4. Binary search

This is a fast method of searching for an item in a sorted / ordered list.

Sometimes, you may be doing a binary search without realising it.

Example

You want to find Samuel Jones in the local telephone book. Would you start at page 1 and then go on from there, page by page? Unlikely.

You don't do this because you know an important fact about telephone books - the entries are in alphabetic order. So what you do is make a guess - J is about halfway down the alphabet and so you open the telephone book around half way. The page you see has names starting with N. So you know J will be in the first half of the book. Next you open a page about halfway down the first half - the page has 'H'. So now Jones must be in the upper half of this section.
You are carrying out a 'Binary search' algorithm. Notice that after only two guesses you are getting much closer to the answer. If you were carrying out a serial search, you would still be at page 2.

Binary Search algorithm

1. Set the highest location in the list to be searched as N
2. Set the lowest location in the list to be searched as L
3. Examine the item at location (N - L) /2 (i.e. halfway)
4. Is it a match? if Yes End search.
5. No
6. Is item less than criteria ?
7. If Yes, Set lower limit L to item + 1 (Force the next search to use the upper half)
8. If No, Set upper limit N to item - 1 (Force the next search to use the lower half)
9. Is lower limit = upper limit, if yes end search (no match found)
10. Repeat from step 3 with the new upper and lower bounds.
    

Is Binary searching better than serial searching?

It depends.
1. If the list is large and changing often, with items constantly being added or deleted, then the time it takes to constantly re-order the list to allow for a binary search might be longer than a simple serial search in the first place.
2. If the list is large and static e.g. telephone number database, then a binary search is very fast compared to linear search. (in maths terms it takes 2log₂(n) for a binary search over n items)
3. If the list is small then it might be simpler to just use a linear search
4. If the list is random, then linear is the only way
5. If the list is skewed so that the most often searched items are placed at the beginning, then on average, a linear search might be better.