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

The algorithm repeatedly examines the element at the middle index and uses it to
trim the range of indexes of interest in half. If we examine the middle element and
find it's too small, we will eliminate all elements between min and mid from consid-
eration. If the middle element is too large, we will eliminate all elements between
mid and max from consideration.
Consider the following array:

int[] numbers = {11, 18, 29, 37, 42, 49, 51, 63,
69, 72, 77, 82, 88, 91, 98};

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14

11 18 29 37 42 49 51 63 69 72 77 82 88 91 98

Let's run a binary search on the array for a target value of 77 . We'll start at the
middle element, which is at index (14 / 2), or 7. The following diagrams show the
min , mid , and max at each step of the algorithm:

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14

11 18 29 37 42 49 51 63 69 72 77 82 88 91 98

min mid max

observation: numbers[7] < 77
decision: search indexes 8 - 14

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14

11 18 29 37 42 49 51 63 69 72 77 82 88 91 98

min mid max

observation: numbers[11] > 77
decision: search indexes 8 - 10

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14

11 18 29 37 42 49 51 63 69 72 77 82 88 91 98

min mid max

observation: numbers[9] > 77
decision: search index 10

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14

11 18 29 37 42 49 51 63 69 72 77 82 88 91 98

min
mid
max

observation: numbers[9] == 77
decision: return 10