GCSE Computer Science/Search Algorithms

Linear Search edit

If you have a list (or array) that is not sorted, then the simplest searching algorithm is linear search. It goes through the list item by item and compares to the item being searched for. If a comparison succeeds, the algorithm has found the item. If all comparisons fail, the item doesn't exist in the array or list. In the simplest variant, the algorithm returns a boolean to indicate success or failure.

Exercise: Linear Search

Consider the list of strings "Cat","Mouse","Frog","Lion","Panda","Llama","Bee", in this order. How many comparisons would it take to find "Panda"?

Answer:

5

And how many when searching for "Camel"?

Answer:

It would take 7 to reach the conclusion the string is not in the list.

Binary Search edit

As the last question points out, a linear search may take as many comparisons as there are items in the list, so searching for a name among a list of several million names (e.g. the electoral register of a country) could take a very long time.

If your list is in ascending order, or is put in ascending order by a sorting algorithm, then you can perform a binary search. This involves splitting the data into half at each comparison, thereby 'zooming in' more quickly into the part of the list where the item must be, if it exists in the list. This results in much better performance.

Let's search for the name Miles in the following sorted list:

Ali, Bernie, Claire, Mohammed, Peter, Simon, Yvonne

We compare Miles to the middle name, Mohammed:

Ali, Bernie, Claire, Mohammed, Peter, Simon, Yvonne

Miles comes alphabetically before Mohammed, so we know that Miles won't be to the right of Mohammed. We can thus 'throw away' the right half of the list:

Ali, Bernie, Claire, ~~Mohammed, Peter, Simon, Yvonne~~

We now compare Miles to the middle name in the remaining list, Bernie:

Ali, Bernie, Claire, ~~Mohammed, Peter, Simon, Yvonne~~

Miles comes alphabetically after Bernie, so we can throw the left hand side away:

~~Ali, Bernie~~, Claire, ~~Mohammed, Peter, Simon, Yvonne~~

Finally we compare Miles to the middle name of this single item list, Claire:

~~Ali, Bernie~~, Claire, ~~Mohammed, Peter, Simon, Yvonne~~

Miles isn't the same as Claire, there are no more items to compare so we know that Miles isn't in the list.

This only took 3 comparisons using binary search, it would have taken 7 using linear search. It gets even better when the list is large. For example, a 1,000,000,000 item list would only take a maximum of 30 comparisons using binary search! It's very useful to have sorted data.

Exercise:Linear vs Binary Search

Sorted data is also useful for linear search. How could a modified linear search algorithm make fewer than 7 comparisons when searching Miles?

Answer:

The modified linear search would know after 4 comparisons (against Ali, Bernie, Claire and Mohammed) that Miles is not in the sorted list, because Miles should have appeared before Mohammed.

For the list of 7 names shown above, can you think of a case where linear search is faster than binary search?

Answer:

If we search for the first item in the list, Ali, binary search still takes 3 comparisons (against Mohammed, Bernie and Ali) but linear search only needs 1 comparison.

For linear search of a large list, the best case is if the sought item is in the first position. What is the best case for binary search of a large list?

Answer:

Binary search only requires 1 comparison If the sought item is in the middle of the list.

A binary search locates the position of an item in a sorted array. After each unsuccessful comparison, binary search reduces the search space by half. How efficient is it? How many searches for x number of items? What is the equation? Why is it better than a linear search.

How to work out the maximum number of searches (n) on a x sized array:

 2^n > size of list (x) where n = max searches

For example, if we had a 3 item array

2^2 = 4 > 3 therefore max searches = 2

Exercise: Binary Search

Given a 256 item sorted list, what is the maximum number of searches needed to find an item?

Answer:

9 as:

2^n > size of list where n = max searches
2^9 = 512 > 256

Given a 1000 item sorted list, what is the maximum number of searches needed to find an item?

Answer:

10 as: 
2^n > size of list where n = max searches
2^10 = 1024 > 1000