Java Reference
In-Depth Information
LISTING 10.12
continued
while
(!found && min <= max)
{
mid = (min+max) / 2;
if
(list[mid].compareTo(target) == 0)
found =
true
;
else
if
(target.compareTo(list[mid]) < 0)
max = mid-1;
else
min = mid+1;
}
if
(found)
return
list[mid];
else
return null
;
}
}
Consider the following sorted array of integers:
0
10
1
12
2
18
3
22
4
31
5
34
6
40
7
46
8
59
9
67
10
69
11
72
12
82
13
84
14
98
Suppose we were trying to determine if the number 67 is in this list. Initially, the
target might be anywhere in the list, or not at all. That is, at first, all items in the
search pool are
viable candidates
.
Instead of starting the search at one end or the other, a binary search begins
in the middle of the sorted list. If the target element is not found at that middle
element, then the search continues. The middle element of this list is 46, which is
not our target, so we must search on. However, since the list is sorted, we know
that if 67 is in the list, it will be in the later half of the array. All values at lower
indexes are less than 46. Thus, with one comparison, we've taken half of the data
out of consideration, and we are left with the following viable candidates:
Viable Candidates
0
10
1
12
2
18
3
22
4
31
5
34
6
40
7
46
8
59
9
67
10
69
11
72
12
82
13
84
14
98
Search WWH ::
Custom Search