<< Introduction to algorithms >> ( Second Edition )
Exercise 2.3-5
Referring back to the searching problem ( see Exercise 2.1-3 ), observe that if the
sequence A is sorted, we can check the midpoint of the squence against v and
eliminate half of the sequence from further consideration. Binary search is an
algorithm that repeats this procedure, halving the size of remaining portion of
the sequence each time. Write pseudocode, either iterative or recursive, for binary
search. Argue that the worst-case running time of binary search is O( nlgn )
Solution:
// 声明：本代码旨在实现原文的思想
// copyleft 2004 http://blog.csdn.net/mskia
// email: bitrain@hotmail.com
#ifndef Binary_Search_by_mskia
#define Binary_Search_by_mskia
namespace te {
template< class T >
T *binary_search( const T &target , T *first , T *last ) {
while ( first <= last ) {
T *mid = first + ( ( last - first ) >> 1 );
if ( *mid == target ) {
return mid;
} else if ( target < *mid ) {
last = mid - 1;
} else {
first = mid + 1;
}
}
return NULL;
}
}
#endif