Java Reference
In-Depth Information
Display 11.9
Iterative Version of Binary Search
★
1
/**
−
2
1 is
3
returned. Otherwise returns an index in the segment such that key == a[index].
4
Precondition: a[lowEnd] <= a[lowEnd + 1]<= ... <= a[highEnd]
5
*/
6
public static int
search(
int
[] a,
int
lowEnd,
int
highEnd,
int
key)
7{
8
Searches the array a for key. If key is not in the array segment, then
int
first = lowEnd;
9
int
last = highEnd;
10
int
mid;
11
boolean
found =
false
;
//so far
12
int
result = 0;
//to keep compiler happy
13
while
( (first <= last) && !(found) )
14
{
15
mid = (first + last)/2;
16
if
(key == a[mid])
17
{
18
found =
true
;
19
result = mid;
20
}
21
else if
(key < a[mid])
22
{
23
last = mid
−
1;
24
}
25
else if
(key > a[mid])
26
{
27
first = mid + 1;
28
}
29
}
30
if
(first > last)
31
result =
−
1;
32
return
result;
33
}
often makes sense to derive a recursive algorithm even if you expect to later convert it to
an iterative algorithm. You can see the iterative method from Display 11.9 embedded in
a full demonstration in the files
IterativeBinarySearch.java
and
IterativeBinary-
SearchDemo.java
on the accompanying CD.
extra code
on CD
