Binary Search

static int binarySearch(int[] A, int N) {
// Searches the array A for the integer N.
// A is assumed to be sorted into increasing order.

int lowestPossibleLoc = 0;
int highestPossibleLoc = A.length - 1;

while (highestPossibleLoc >= lowestPossibleLoc) {
int middle = (lowestPossibleLoc + highestPossibleLoc) / 2;
if (A[middle] == N) {
// N has been found at this index!
return middle;
}
else if (A[middle] > N) {
// eliminate locations >= middle
highestPossibleLoc = middle - 1;
}
else {
// eliminate locations <= middle
lowestPossibleLoc = middle + 1;
}
}

// At this point, highestPossibleLoc < LowestPossibleLoc,
// which means that N is known to be not in the array. Return
// a -1 to indicate that N could not be found in the array.

return -1;

}