Here is a list:
Suppose we want to do a binary search for the value 551:
Pointers which keep track of the possible range where our search value might
be:
Loop invariant: If the search item is in the list at all, it is between
the "low" and "high" items (inclusive).
Examine the item in the middle:
Since 551 < 603, move the "high" pointer down.
Examine the item in the middle:
Since 551 > 363, move the "low" pointer up.
Examine the item in the middle:
Found!
Now, let's look at a not-found example.
Suppose we're searching for 552. Everything would have gone the same so far.
Since 552 > 551, move the "low" pointer up.
Examine the item in the middle:
Since 552 > 551, move the "low" pointer up.
Since the one item is not 552, we know that 552 is not in the list.
Now, suppose the list wasn't sorted after all?
We wouldn't have done anything any differently in the above (we never looked
at that number 723), so this is the
final state we'd be at;
we would have missed the 552 and made an incorrect conclusion.
The binary search algorithm is only valid on sorted lists.
If you apply the binary search algorithm to an unsorted list, you're not doing
a correct search and you might get the wrong answer.