与排序算法不同，搜索算法是比较统一的，常用的搜索除hash外仅有两种，包括不需要排序的线性搜索和需要排序的binary search。
首先介绍一下binary search，其原理很直接，不断地选取有序数组的组中值，比较组中值与目标的大小，继续搜索目标所在的一半，直到找到目标，递归算法可以很直观的表现这个描述：
int binarySearchRecursive(int A[], int low, int high, int key)
{
if (low > high) return -;
int mid = (low + high) >> ;
if (key < A[mid]) return binarySearchRecursive(A, low, mid - , key);
else if (key > A[mid]) return binarySearchRecursive(A, mid + , high, key);
else return mid;
}
但实际上，递归方法的时间效率和空间效率都不如迭代方法，迭代方法才是常用的binary search，代码如下：
int binarySearch(int A[], int low, int high, int key)
{
int mid;
while (low <= high)
{
mid = (low + high) >> ;
if (key < A[mid]) high = mid - ;
else if (key > A[mid]) low = mid + ;
else return mid;
}
return -;
}
简单计算一下Binary Search的效率：
算法流程：
1.检查上下边界--2.获取中值--3.比较--左半边进入子问题/右半边进入自问题/获得结果
1，2所需时间为常数时间，设为C。3阶段以一半的数据量重新运行函数，所以：
T(n)=T(n/2)+C
设n=2^k，则有T(2^k)=T(2^(k-1))+C=(T(2^(k-2))+C)+C=T(1)+k*C
即T(n)=log(n)*C+T(1)，所以binary search是一个O(log(n))的算法。
测试函数：
void searchTest()
{
int a[] = { ,,,,,,,,,,, };
cout << binarySearch(a, , , ) << endl;
cout << binarySearch(a, , , ) << endl;
cout << binarySearch(a, , , ) << endl;
cout << endl;
cout << binarySearchRecursive(a, , , ) << endl;
cout << binarySearchRecursive(a, , , ) << endl;
cout << binarySearchRecursive(a, , , ) << endl;
}
测试结果如下：
11
-1
-1
11
-1
-1
请按任意键继续. . .
传统C函数中有bsearch这一函数，因为在现代C++中使用C库运行效率很低，加上接口并不好用，不再提及。而STL中，有以下几个关于搜索的函数。他们均作用于各个STL容器。
int count(起始迭代器，终止迭代器，key value)
return key value的数量
iterator find(起始迭代器，终止迭代器，key value)
成功：return 找到的第一个key value的迭代器
失败：return 终止迭代器
bool binary_search(起始迭代器，终止迭代器，key value)
return 是否找到
iterator lower_bound(起始迭代器，终止迭代器，key value)
return 大于或等于key value的第一个迭代器，若所有值都小于key value，返回终止迭代器
iterator upper_bound(起始迭代器，终止迭代器，key value)
return 大于key value的第一个迭代器，若所有值都小于key value，返回终止迭代器
这些函数中，count和find是作用于任意排序对象的，其效率为O(n)，而binary_search, lower_bound, upper_bound是作用于有序对象的，其效率是O(logN)。
下面代码给出这些STL函数的测试：
void searchTest()
{
vector<int> b{ ,,,,,,,,,,, };
cout << "vector<int> b{ 1,2,3,4,4,7,9,11,17,20,23,39 };" << endl;
cout << "count(b.begin(), b.end(), 4):"
<< count(b.begin(), b.end(), ) << endl;
cout << endl;
cout << "find(b.begin(), b.end(), 39) - b.begin():"
<< find(b.begin(), b.end(), ) - b.begin() << endl;
cout << "find(b.begin(), b.end(), 4) - b.begin():"
<< find(b.begin(), b.end(), ) - b.begin() << endl;
cout << "find(b.begin(), b.end(), 37) - b.begin():"
<< find(b.begin(), b.end(), ) - b.begin() << endl;
cout << "find(b.begin() + 5, b.begin() + 10, 39) - b.begin():"
<< find(b.begin() + , b.begin() + , ) - b.begin() << endl;
cout << endl;
cout << "binary_search(b.begin(), b.end(), 39):"
<< binary_search(b.begin(), b.end(), ) << endl;
cout << "binary_search(b.begin(), b.end(), 37):"
<< binary_search(b.begin(), b.end(), ) << endl;
cout << endl;
cout << "lower_bound(b.begin(), b.end(), 39) - b.begin():"
<< lower_bound(b.begin(), b.end(), ) - b.begin() << endl;
cout << "lower_bound(b.begin(), b.end(), 4) - b.begin():"
<< lower_bound(b.begin(), b.end(), ) - b.begin() << endl;
cout << "lower_bound(b.begin(), b.end(), 37) - b.begin():"
<< lower_bound(b.begin(), b.end(), ) - b.begin() << endl;
cout << "lower_bound(b.begin() + 5, b.begin() + 10, 39) - b.begin():"
<< lower_bound(b.begin() + , b.begin() + , ) - b.begin() << endl;
cout << endl;
cout << "upper_bound(b.begin(), b.end(), 39) - b.begin():"
<< upper_bound(b.begin(), b.end(), ) - b.begin() << endl;
cout << "upper_bound(b.begin(), b.end(), 4) - b.begin():"
<< upper_bound(b.begin(), b.end(), ) - b.begin() << endl;
cout << "upper_bound(b.begin(), b.end(), 37) - b.begin():"
<< upper_bound(b.begin(), b.end(), ) - b.begin() << endl;
cout << "upper_bound(b.begin() + 5, b.begin() + 10, 39) - b.begin():"
<< upper_bound(b.begin() + , b.begin() + , ) - b.begin() << endl;
}
测试结果：
vector<int> b{ 1,2,3,4,4,7,9,11,17,20,23,39 };
count(b.begin(), b.end(), 4):2
find(b.begin(), b.end(), 39) - b.begin():11
find(b.begin(), b.end(), 4) - b.begin():3
find(b.begin(), b.end(), 37) - b.begin():12
find(b.begin() + 5, b.begin() + 10, 39) - b.begin():10
binary_search(b.begin(), b.end(), 39):1
binary_search(b.begin(), b.end(), 37):0
lower_bound(b.begin(), b.end(), 39) - b.begin():11
lower_bound(b.begin(), b.end(), 4) - b.begin():3
lower_bound(b.begin(), b.end(), 37) - b.begin():11
lower_bound(b.begin() + 5, b.begin() + 10, 39) - b.begin():10
upper_bound(b.begin(), b.end(), 39) - b.begin():12
upper_bound(b.begin(), b.end(), 4) - b.begin():5
upper_bound(b.begin(), b.end(), 37) - b.begin():11
upper_bound(b.begin() + 5, b.begin() + 10, 39) - b.begin():10
请按任意键继续. . .