## The Binary Search Algorithm

This only applies to a list of names in alphabetical order or a list of numbers in increasing order.

Unordered lists would have a sorting algorithm applied first.

This algorithm concentrates on the midpoint of an ever reducing list.

We define the midpoint of a list of N names, numbered N1, N1+1,...,N2 as [(N1+N2)/2] where [x] = the smallest integer greater than or equal to x

We wish to search the list for a name, Fred, say.

Step 1

The algorithm compares Fred with the middle name in the list.

Either a) the name Fred is found to be at this position,

or b) the name Fred occurs before the middle of the list

or c) the name Fred occurs after the middle of the list

Step 2

If a) occurs, the search is over.

If b) occurs, the search continues with Step 1 on a reduced list consisting of those names before the middle name.

If c) occurs, the search continues with Step 1 on a reduced list consisting of those names after the middle name.

Stop when Fred has been found or when it has been shown that Fred does not appear on the list.

At each stage half of the remaining list is discarded (hence the name of the algorithm).

Example

a) Find the name Robinson in the list below.

b) Find the name Davis in the list below.

1 Bennett

2 Blackstock

3 Brown

4 Ebenezer

5 Fowler

6 Laing

7 Leung

8 Robinson

9 Saludo

10 Scadding

a) The middle name is [(1+10)/2] = [5.5] = 6 Laing

Robinson is after Laing, so the list reduces to

7 Leung

8 Robinson

9 Saludo

10 Scadding

The middle name is [(7+10)/2] = [8.5] = 9 Saludo

Robinson is before Saludo, so the list reduces to

7 Leung

8 Robinson

The middle name is [(7+8)/2] = [7.5] = 8 Robinson

The search is complete and Robinson has been found

b) As before, the middle name is Laing

Davis is before Laing, so the list reduces to

1 Bennett

2 Blackstock

3 Brown

4 Ebenezer

5 Fowler

The middle name is [(1+5)/2] = [3] = 3 Brown

Davis is after Brown, so the list reduces to

4 Ebenezer

5 Fowler

The middle name is [(4+5)/2] = [4.5] = 5 Fowler

Davis is before Fowler, so the list reduces to

4 Ebenezer

The list is now only one item and this item is not Davis

We conclude that Davis is not on the list.