/*
The binary search algorithm assumes that an array A is sorted, such as
2 4 5 8 9 12 15 18
The algorithm searches for an element by breaking the array in half each
time. It is a very efficient algorithm (O(log n) time).
We maintain two variables: start and end, which keeps track of the
current segment of the array we're examining. Initially, start=0 and
end=A.length-1, which indicates the entire array.
The algorithm applies the following steps repeatedly:
Calculate the middle index of the array mi = (start+end)/2
Compare x with element at A[mi]:
if (x==A[mi]) then we've found what we're looking for and can stop.
if (xA[mi]) then start=mi+1;
Finally, if ever start>end, that means that x is not in the
array, and we can quit.
*/
public class bsearch
{
// the following function determines if an array is sorted:
public static boolean sorted(int[] A)
{
boolean answer = true;
for(int i=0;iA[i+1]) answer = false;
}
return answer;
} // sorted
// binary search (using loop): returns position of element, -1 if not found
public static int search(int x, int[] A)
{
int start=0;
int end=A.length-1;
int mi=0;
boolean stop = false;
while (!stop)
{
mi = (start+end)/2;
if (start>end) {stop=true; mi=-1;}
else if (x==A[mi]) { stop = true; }
else if (xend) return -1; // not found;
int mi= (start+end)/2;
if (A[mi]==x) return mi;
else if (x