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.

For example, you want to find Samuel Jones in the local telephone book. Would you start at page 1 and then go on from there? 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.
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 flow diagram

Set the highest location in the list to be searched of the list (N)
Set the lower location in the list to to be searched (L)

1. Examine the item at location (N - L) /2
2. Is it a match -> Yes End search. -> No
3. Is item < search -> Yes - > Set lower limit L to item + 1. -> No
set upper bound to current item location - 1
4. Is current item = end of list Yes - No match found.
4. Repeat

Serial Search
This method starts at the first item in the list, checks for a match. If no match is found then move to the next item. Repeat this process either until a match is found or the end of the list has been reached.
The advantage of a serial search is that the list does not have to be in any particular order, unlike a binary search that depends on the list being in a certain order. The disadvantage of serial search is that the maximum time to find an item in a list goes up linearly with the length of the list.

Search time:
Binary = 2Logn(n)
Serial = n+1

Which is the best method?
It depends.
1. If the list is large and changing often, with items constantly added or deleted, then the time it takes to re-order the list to allow for a binary search every time might be longer than a simple serial search.
2. If the list is large and static e.g. telephone number database then a binary search is very efficient compared to linear search.
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.

2020-10