Searching and Sorting - Building Java Programs: A Back to Basics Approach - page 795

What about when we're searching for an element that isn't found in the array?
Let's say we're searching for the value 78 instead of 77 . The steps of the algorithm
will be the same, except that on the fourth pass the algorithm will reach 77 instead of
the desired value, 78 . The algorithm will have eliminated the entire range without
finding the target and will know that it should stop. Another way to describe the
process is that the algorithm loops until the min and max have crossed each other.
The following code implements the binary search algorithm. Its loop repeats until
the target is found or until the min and max have crossed:

// Binary search algorithm.
// Returns an index at which the target
// appears in the given input array, or -1 if not found.
// pre: array is sorted.
public static int binarySearch(int[] numbers, int target) {
int min = 0;
int max = numbers.length - 1;
while (min <= max) {
int mid = (max + min) / 2;
if (numbers[mid] == target) {
return mid; // found it!
} else if (numbers[mid] < target) {
min = mid + 1; // too small
} else { // numbers[mid] > target
max = mid - 1; // too large

}

}
return -1; // not found

}

We won't bother to show a runtime chart for the binary search algorithm, because
there would be nothing to draw on the chart. This algorithm is so fast that the computer's
clock has trouble measuring its runtime. On a modern computer, even an array of over
100,000,000 elements registers as taking 0 ms to search!
While this is an impressive result, it makes it harder for us to empirically examine
the runtime. What is the complexity class of the binary search algorithm? The fact
that it finishes so quickly tempts us to conclude that it's a constant-time, or O (1),
algorithm. But it doesn't seem right that a method with a loop in it would take a con-
stant amount of time to execute. There is a relation between the runtime and the input
size, because the larger the input is, the more times we must divide our min - max
range in half to arrive at a single element. We could say that 2 raised to the number of
repetitions is approximately equal to the input size N:

2 repetitions

N