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 Pseudo Code
Reference [1] http://en.wikipedia.org/wiki/Binary_search_algorithm |
© The University of Hong Kong Algorithms Library - hkual@cs.hku.hk |