2.1 Binary Search

Binary Search algorithm in general should be the first algorithm about Divide-and-Conquer for Computer Science student. Sometimes Binary Search is also called "Half-Interval Search" or "Dichotomic Search" algorithm. Different to the general Linear Search, Binary Search works only in a sorted array, certainly for an unsorted array it is no way but only to scan all elements so Linear Search is already optimal. The idea of Binary Search is that, in a sorted array, if the current element is not the target, then the target must be either in the left hand side or right hand side, but not both, which depends on the target is less than or greater than the current element, so Divide-and-Conquer will be a way to do so.

Time Complexity
In each recursive step half of the number of computation can be reduced, so the time complexity is O(log n)

Pseudo Code

BinarySearch( Array[0..n-1], target, lower, upper )
   if lower > upper then
       return "Not Found"
   var mid = (lower + upper) / 2
   if Array[mid] == target then
       return mid
   else if Array[mid] > target then
       return BinarySearch( Array, target, lower, mid-1 )
   else if Array[mid] < target then
       return BinarySearch( Array, target, mid+1, upper )

Reference [1] http://en.wikipedia.org/wiki/Binary_search_algorithm

© The University of Hong Kong Algorithms Library - hkual@cs.hku.hk