Programming and Problem Solving with Java

11.6 S e a rching | 555

ant

cat

chicken

cow

deer

dog

fish

goat

horse

rat

snake

[0]

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[0]

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[0]

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[0]

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

first

middle

last

First iteration

bat < dog

ant

cat

chicken

cow

deer

dog

fish

goat

horse

rat

snake

first

middle

last

Second iteration

bat < chicken

(a) (b)

(c) (d)

bat cannot be

in this part

of the list

bat cannot be

in this part

of the list

ant

cat

chicken

cow

deer

dog

fish

goat

horse

rat

snake

first and middle

last

Third iteration

bat > ant

ant

cat

chicken

cow

deer

dog

fish

goat

horse

rat

snake

first, last,

and middle

Fourth iteration

bat < cat

bat cannot be

in this part

of the list

Figure 11.10 Walk-through of Binary Search Algorithm