Binary search is an algorithm that finds the position of a search target in a sorted array. It has an worst case run time of logN (for 1 million items, 20 probes can do), which makes it pretty efficient in searching. This post briefly describes binary search and provides two implementations with the same interface as C standard library bsearch() function.
Binary search is a divide and conquer search algorithm. It consists of zero or more probes. At each probe, it first compare the search target (key) with the middle element, if the key is smaller than the middle element, it reduces the search space to the lower half; if it’s bigger, it reduces the search space to upper half; if equal, the search is ended. When the search space is reduced to 0 size, the search fails.
Binary search can be implemented in recursion or iteration. Below are two implementations in recursion and iteration respectively. I used the same interface as C standard library,
where key points to the search target; base is the pointer to first item of the search space, which has n items, each item is size number of bytes; the last parameter is a function that compares the two items. It must return negative value if first item is less than second, zero if equal and positive if greater.
Below is the recursion version,
Below is the iteration version,
Both programs accepts three input parameters, the starting search value, the search space size and the search target. For example, if ./bsearch 100 12345 120, it means the sorted array contains value [100, 100+12345-1], and we’re trying to search for 120 from the sorted array.
A execution of either programs with command (./bsearch 100 12345 120) produces the following output,
search 120: found 120 in 13 probes
Some Practical Notes
Although binary search has faster run time compared with linear search, it might not out-perform linear search under all situations. This is because binary search access the data randomly, thus perform poorly in terms of memory access.
A common practice is to switch to linear search when the search space size reduces to 8, 16 or even more depends on your computers. Another approach people use to speed up binary search is to store the first few accessed values (N/2, N/4, 3N/4, etc. ) in a separate array and access them sequentially.
The practical notes are summarized from wikipedia.
1. Wikipedia, Binary search algorithm: http://en.wikipedia.org/wiki/Binary_search
2. C Standard Library Reference: http://www.utas.edu.au/infosys/info/documentation/C/CStdLib.html