Java Reference
In-Depth Information
Display 11.9
Iterative Version of Binary Search
★
1
/**
2
Searches the array a for key. If key is not in the array segment, then
3 -
1
is
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
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 }
illustrates, it 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
IterativeBinarySearchDemo.java
on the accompanying website.
extra code
on website
