previous |
start |
next
Binary Search
- Suppose we want to search the following data
for 123.
|
v[0]
|
v[1]
|
v[2]
|
v[3]
|
v[4]
|
v[5]
|
v[6]
|
v[7]
|
|
14
|
43
|
76
|
100
|
115
|
290
|
400
|
511
|
- The last point in the first half of the data
set, v[3], is 100. That means we should look in the second
half for a match.
|
v[4]
|
v[5]
|
v[6]
|
v[7]
|
|
115
|
290
|
400
|
511
|
- The last value in the first half of this
sequence is 290; hence, the value must be located in the
sequence
- The last value of the first half of this very
short sequence is 115, which is smaller than the value we are
searching for, so we must look in the second half.
- Since there is only one element, the search
easily shows that there is no match.
previous |
start |
next