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.