[tail] [up]

3.10.1 Binary Search

Knowledge Base > Algorithm > Searching

Overview

A binary searchis a searching algorithm for finding a particular value in a sorted list. This algorithm is an example of divide and conquer algorithm (of method 3.7.3.1). In most cases, this algorithm is considered to run better performance than linear search, since it runs at logarithmic time, O(lg n).

Algorithm

Pseudocode

Binary-Search(A,l,h,key)
1 m = (l + h)∕2

2 if A[m] > key

3    then return Binary-Search(A,l,m - 1,key)

4 else if A[m] < key

5    then return Binary-Search(A,m + 1,h,key)

6    else return m

This algorithm is performed by comparing the median element in a list to the one you are searching for, and deciding if the median element is greater than, less than, or equal to the target. The result that the median turns out to be too high becomes the top half of the list, and one too low the becomes bottom half of the list. In the next round, the next median is halfway of the new list. Repeat finding the median of the new sub-list, until the match is found and returned or return -1 if not found. Either case, the size of the last sub-list is 1, in the worst case.

Complexity Analysis

The recurrence function is defined as follow:

( || Θ (1) if n = 1 T(n) = { (3.10.1) || 2 ⋅T(n2)+ Θ (1) if n > 1 (
Let us first see how to illustrate this recursive relation in tree model:
| c = 2c0 c | | | c= c1- c c | 2 2 2 | c -c c c c lg(n+ 1) 4 = 22 4 4 4 c | | | ... ... ... ... ... ... ... ... c | - - - - - - - - | - - - - - - - - c = 2lcgn c c c c c c c c

The total is c ⋅ lg n + c
T(n) = T(1) + c ⋅ lg n = Θ(lg n)
Next, we apply divide and conquerer method (of method 3.7.3.1) to solve the recurrence,

T(n) = 2 ⋅T(n) +c 2 n c = 2 ⋅[2 ⋅T(-)+ -]+ c n 4 2 = 4 ⋅T(4) +2 ⋅c n- c = 4 ⋅(2 ⋅T(8) + 4)+ 2⋅c = 8 ⋅T(n) +3 ⋅c 8 = ... n = 2k ⋅T(-k)+ k ⋅c lgn 2 n k = 2 ⋅T(2lgn)+ lgn⋅c (2 = n ⇒ k = log2n) = ... = T (1) + c⋅lg(n) = Θ (lgn)
For each iteration, the algorithm narrows the search space by a factor 2, and, thus, in the worst case, 1 + log 2n iterations are needed to return an answer. Binary Search Tree is exactly an recursive tree method for binary search, where child node represents cost of subproblems that cut the original problem in half. We sum the costs at each level of the tree to determine the total cost of all levels of recursion, which ends up to be O(h) time , where h is the height of tree and is the factor of log n.

Source Code

Binary Search is usually implemented using recursion or iteration, and here are both implementations, written in C and Scheme:

Related Topics

[front] [up]