Java Reference
In-Depth Information
FIGURE 18-6
A recursive binary search of a sorted array that (a) finds its
target; (b) does not find its target
(a) A search for 8
Look at the middle entry, 10:
2
7
18
4
5
8
10
12
15
21
24
26
0
1
2
3
4
5
7
8
9
6
10
11
8
10, so search the left half of the array.
Look at the middle entry, 5:
2
0
4
1
5
2
7
3
8
4
8
5, so search the right half of the array.
Look at the middle entry, 7:
7
3
8
4
8
7, so search the right half of the array.
Look at the middle entry, 8:
8
4
8
8, so the search ends. 8 is in the array.
(b) A search for 16
Look at the middle entry, 10:
2
0
4
1
5
2
7
3
8
4
10
5
12
6
15
7
18
8
21
9
24
10
26
11
16
10, so search the right half of the array.
Look at the middle entry, 18:
12
6
15
18
8
21
9
24
10
26
11
7
16
18, so search the left half of the array.
Look at the middle entry, 12:
12
15
7
6
16
12, so search the right half of the array.
Look at the middle entry, 15:
15
7
16
15, so search the right half of the array.
The next subarray is empty, so the search ends. 16 is not in the array.
