折半查找
又称为二分查找。这种查找方法要求查找表的数据是线性结构保存，并且还要求查找表中的数据是按关键字由小到大有序排列。
折半查找（二分查找）是一种简单而又高效的查找算法，其查找长度至多为㏒2n+1（判定树的深度），平均查找长度为㏒2(n+1)-1，效率比顺序查找要高，但折半查找只能适用于顺序存储有序表（如对线性链表就无法有效地进行折半查找）。
经典非递归算法实现
int Binary_Search(int search_table[], int key, int low ,int high)
{
while(low <= high)
{
mid = (low + high) / 2;
if(search_table[mid] < key)
{
low = mid + 1;
}
else if(search_table[mid] > key)
{
high = mid - 1;
}
else
{
return mid;
}
}//while
return -1;
}
经典递归算法实现
int Binary_Search(int search_table[], int key, int low ,int high)
{
if(low > high)
{
return -1;
}
int mid = (low + high) / 2;
if(search_table[mid] == key)
{
return mid;
}
else if(search_table[mid] < key)
{
Binary_Search(search_table, key, mid + 1, high);
}
else
{
Binary_Search(search_table, key, low, mid - 1);
}
}
不过，由于折半查找的前提条件是需要有序表顺序存储，对于静态查找表，一次排序后不再变化，这样的算法已经比较好了。但是对于频繁执行插入或删除操作的数据集来说，维护有序的排序会带来不小的工作量，那就不建议使用了。
说一个小的知识点：
mid = (first + last) / 2; //等价于 mid = first + (last - first) / 2;
如果把一个有序的线性数组放到一个二维数组中，那么同样可以利用二分查找：
在这个数组上面查找
bool searchMatrix(vector<vector<int>>& matrix, int target)
{
bool found = false;
int m = matrix.size();//行数
int n = matrix[0].size();//列数
int first = 0;
int last = m * n - 1;
while(first <= last)
{
int mid = (first + last) / 2;
if(matrix[mid / n][mid % n] == target)
{
found = true;
break;
}
else if(matrix[mid / n][mid % n] > target)
{
last = mid - 1;
}
else
{
first = mid + 1;
}
}//while
return found;
}
折半查找扩展
折半查找的思想其实就是，每次查找之后，能缩小下次查找的范围，这一点很重要。以后所有的查找问题，只要是在有序的线性表上查找或者半有序的线性表上查找，都要往折半查找上靠拢，想着每次查找之后，能缩小下次查找的范围。
在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。 请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
只要遇到了有序的查找，就往折半查找上想办法，同时想着怎么能缩小下次查找的范围。
bool searchMatrix(vector<vector<int>>& matrix, int target)
{
int row = matrix.size();
int column = matrix[0].size();
bool found = false;
int i = 0;
int j = column - 1;
while(i < row && j >= 0)
{
if(matrix[i][j] > target)
{
--j;
}
else if(matrix[i][j] < target)
{
++i;
}
else
{
found = true;
break;
}
}//while
return found;
}
这里存储二维数组用的是vector，当然也可以用一个int类型的指针，然后通过行数和列数访问二维数组每一个元素。