Binary Search

A binary search can be used on an array that has been sorted into ascending or descending order.
Binary Search
The algorithm for a binary search is as follows:

★ Compare the searched for value to the middle array item

☆ if value == middle then quit. You've found it.

☆ else if value < middle then consider the sublist making up the first half of the array (before the middle item)

☆ else if value > middle then consider the sublist making up the last half of the array (after the middle item)

★ If you didn't find the value, repeat the search on the sublist.

★ You are done as soon as you find the item or whenever the sublist that you are supposed to search is empty.

int BinarySearch(int a[], int aSize, int toFind) { int start = 0; //the search starts with index 0 int last = aSize -1; //last is the last array index while (start <= last) //while there is still a place to look. { int middle = (start + last) / 2; //Look here first if (toFind == a[middle]) //Found item. Quit. return middle; if (toFind > a[middle]) //Look in the last half start = middle + 1; else //OR look in the first half last = middle - 1; } //the element wasn't found return -1; }
binarySearch.cpp

Example

We have a list of integer values: int list[12] = {-2,1,2,3,5,7,8,10,14,15,38,61}; (1) Suppose we wish to search this one-dimensional array for the value 10: int index = BinarySearch(list,12,10); The figure below, shows how binary search works:.

1st

↓

-2 1 2 3 5 7 8 10 14 15 38 61

0 1 2 3 4 5 6 7 8 9 10 11

start middle last

1st 2nd

↓ ↓

-2 1 2 3 5 7 8 10 14 15 38 61

0 1 2 3 4 5 6 7 8 9 10 11

start middle last

1st 3rd 2nd

↓ ↓ ↓

-2 1 2 3 5 7 8 10 14 15 38 61

0 1 2 3 4 5 6 7 8 9 10 11

start/middle last

1st 3rd 4th
stop here 2nd

↓ ↓ ↓ ↓

-2 1 2 3 5 7 8 10 14 15 38 61

0 1 2 3 4 5 6 7 8 9 10 11

start/middle/last

After control returns to the activating function, index will contain 7.
(2) Suppose we wish to search this one-dimensional array for the value 25: int index = BinarySearch(list,12,25); The figure below, shows how binary search works:.

1st

↓

-2 1 2 3 5 7 8 10 14 15 38 61

0 1 2 3 4 5 6 7 8 9 10 11

start middle last

1st 2nd

↓ ↓

-2 1 2 3 5 7 8 10 14 15 38 61

0 1 2 3 4 5 6 7 8 9 10 11

start middle last

1st 2nd 3rd

↓ ↓ ↓

-2 1 2 3 5 7 8 10 14 15 38 61

0 1 2 3 4 5 6 7 8 9 10 11

start middle last

1st 2nd 4th
stop here 3rd

↓ ↓ ↓ ↓

-2 1 2 3 5 7 8 10 14 15 38 61

0 1 2 3 4 5 6 7 8 9 10 11

start/middle/last

After control returns to the activating function, index will contain -1 meaning that the function did not find 25 in the array.
Application Examples

★ IRS database keyed by social security number

★ DMV records keyed by driver's license numbers

Binary or Linear search
Why use a binary search when a linear search is easier to code? The answer lies in the efficiency of the search. With a linear search, if you double the size of a list, you could potentially take twice as much time to find an item. With a binary search, doubling the size of the list merely adds one more item to look at. Each time you look with a binary search, you eliminate half of the remaining list items as possible matches.

					1st	3rd	4th stop here	2nd
					↓	↓	↓	↓
-2	1	2	3	5	7	8	10	14	15	38	61
0	1	2	3	4	5	6	7	8	9	10	11
							start/middle/last