同样的，二分查找很好理解，不多做解释，要注意二分查找的list必须是排好序的。
这里实现了两种二分查找的算法，一种递归一种非递归，看看代码应该差不多是秒懂。想试验两种算法，改变一下findFunc函数指针（auto findFunc = RecursionBinaryFind; //BinaryFind ）即可。
时间复杂度：O(lgn)
空间复杂度：O(1)
除了顺序查找和二分查找，还有一些需要借助某些数据结构才能进行查找的算法，例如：分块查找，二叉排序树查找，哈希查找，B树/B+树/B*树查找等，这些算法的重点更偏向于数据结构本身，因而将放在数据结构部分进行示例。
show me the code ！
// #if __cplusplus < 201103L // #error "must be compiled under c++11 support platform!!!" // #endif #include <iostream> #include <algorithm> #include <iterator> #include <cassert> using namespace std; //WARNING : input varList of function RecursionBinaryFind must be sorted!!! int RecursionBinaryFindImp(const int varList[], const int begin,const int end, const int target) { if (!varList || begin > end) { return -1; } int index = -1; int mid = (begin + end) >> 1; if (target == varList[mid]) { index = mid; } else if (target < varList[mid]) { index = RecursionBinaryFindImp(varList,begin,mid - 1,target); } else if (target > varList[mid]) { index = RecursionBinaryFindImp(varList, mid + 1, end, target); } return index; } int RecursionBinaryFind(const int varList[], const int size, const int target) { if (!varList || size < 0) { return -1; } return RecursionBinaryFindImp(varList,0,size-1,target); } //WARNING : input varList of function SequentialFind must be sorted!!! int BinaryFind(const int varList[], const int size, const int target) { if (!varList || size < 0) { return -1; } int index = -1; int begin = 0; int end = size - 1; int mid = (begin + end) >> 1; while (begin<end) { if (target == varList[mid]) { break; }else if (target < varList[mid]) { end = mid - 1; }else if (target > varList[mid]) { begin = mid + 1; } mid = (begin + end) >> 1; } index = mid; return index; } void test() { //case counter int testCase = 0; //find function object auto findFunc = RecursionBinaryFind; //BinaryFind //show case result lambda function auto showFunc = [&testCase](){cout << "case[" << testCase++ << "] ok... "<<endl; }; cout << "test begin : " << endl << endl; //case empty list { assert(-1 == findFunc(nullptr, 0, 0)); showFunc(); } //case wrong list size { const int testList[] = { -12, -3, 0, 1, 2, 3, 12, 34, 56 }; assert(-1 == findFunc(testList, 0, 0)); showFunc(); } //case not found { const int testList[] = { -12, -3, 0, 1, 2, 3, 12, 34, 56 }; const int size = sizeof(testList) / sizeof(int); const int target = -33; assert(-1 == findFunc(testList, 0, 0)); showFunc(); } //case found at begin position { const int testList[] = { -12, -3, 0, 1, 2, 3, 12, 34, 56 }; const int size = sizeof(testList) / sizeof(int); const int target = -12; assert(0 == findFunc(testList, size, target)); showFunc(); } //case found at random position { const int testList[] = { -12, -3, 0, 1, 2, 3, 12, 34, 56 }; const int size = sizeof(testList) / sizeof(int); const int target = 1; assert(3 == findFunc(testList, size, target)); showFunc(); } //case found at end position { const int testList[] = { -12, -3, 0, 1, 2, 3, 12, 34, 56 }; const int size = sizeof(testList) / sizeof(int); const int target = 56; assert(size - 1 == findFunc(testList, size, target)); showFunc(); } cout <<endl<< "test done ! " << endl << endl; } int main(int argc, char* argv[]) { test(); return 0; }