Cutting the interval in two

Imagine you are looking for a word in a paper dictionary. You do not read page by page from the beginning: you open in the middle, look whether the word sought is before or after, then start again on the remaining half. This is exactly the principle of binary search: it works ONLY on an already-sorted array, and it eliminates half the candidates at each step.

We keep two bounds, left and right, that delimit the zone where the value sought (the « target ») can still be. We compute the middle of this zone, we compare the value at that index with the target: if they are equal, we have found it; if the middle value is smaller than the target, the target can only be to the right of the middle (we move left); otherwise it can only be to the left (we move right).

Let us follow the interval [left, right] shrink while searching for the value 25 in the sorted array of odd numbers from 1 to 31 (indices 0 to 15):

array (index:value) : 0:1 1:3 2:5 3:7 4:9 5:11 6:13 7:15 8:17 9:19 10:21 11:23 12:25 13:27 14:29 15:31

step 1 : [left=0  ......middle=7(value 15)...... right=15]   (15 < 25 -> keep the right half)
step 2 :            [left=8...middle=11(value 23)... right=15]   (23 < 25 -> keep the right half)
step 3 :                        [left=12.middle=13(value 27). right=15]   (27 > 25 -> keep the left half)
step 4 :                        [left=12=middle=right=12(value 25)]   (found!)

In only 4 steps, we found the value among 16 elements, whereas a linear search could have needed up to 16 comparisons. That is the whole strength of binary search: dividing the search zone by two at each step instead of exploring it element by element.