Binary Search Algorithm

Profile manager: Roy Walmsley [send private message]

Introduction

The binary search, also known as half-interval search is used to find a specific value in a list of sorted values. Such a sorted list could be, for example, all the integer numbers from zero to one thousand inclusive, or all the dates in a year. It is this latter one that is particularly useful for genealogists.

Principle of Operation

Let's say we have an event which we know has a specific date, but we don't know what that date is, other than knowing the year. However, we do have the ability to search across a range of dates to see if the event is present, the range being adjustable, eventually down to a single date.

Step 1
Set the search range to half the unknown interval, which is one year. Hence search in the first six months. If the result is found, then it lies in the first six months. If not, it is in the second six months.

Step 2
Set the search range to half the unknown interval, which is now six months. Hence, search in the first three of those six months. If the result is found, then it lies in the first of those three months. If not, it is in the second of those three months.

Step 3
Set the search range to half the unknown interval, etc.

Step 4
Repeat this half interval search process until down to a single day, at which point the date will be known.

How many steps will it take? Theoretically, for a one year interval, nine.

Example

This will be illustrated with a specific example - the date won't be revealed until the end, to mimic real life.

Step 1
Searching over the period 1 January to 30 June inclusive - result not found. Hence the date is in the second half of the year.

Step 2
Searching over the period 1 July to 30 September inclusive - result not found. Hence the date is in the last quarter of the year.

Step 3
Searching over the period 1 October to 15 November inclusive - result found.

Step 4
Searching over the interval 1 October to 22 October inclusive - result not found.

Step 5
Searching over the interval 23 October to 4 November inclusive - result found.

Step 6
Searching over the interval 23 October to 28 October inclusive - result found.

Step 7
Searching over the interval 23 October to 25 October inclusive - result found.

Step 8
Searching over the interval 23 October to 24 October inclusive - result not found.

Conclusion
The date was 25 October.

Verification
Search the specific date 25 October - result found.

Usage

Web sites where this procedure is known to be successful:

• New South Wales, Australia, Registry of Births, Deaths and Marriages