目录
二分查找
1.简介
二分查找也是有特殊情况的，比如数列本身是有序的。这个有序数列是怎么产生的呢？有时它可能本身就是有序的，也有可能是通过排序算法得到的。
不管其他情况，就先假设这一数组是有序的，接下来二分查找就该登场了。
二分查找（Binary Search）也叫作折半查找。二分查找有两个要求，一个是数列有序，另一个是数列使用顺序存储结构（比如数组）。
2.例子
废话不多说，直接上例子：
假设已经排序好的一组数{5,12,15,19,22,35,36,40,67,78,82}
假设我们要找的元素是k=40；
如图1，我们先找到这组数的第一个数和最后一个数的下标，定义第一个为 left，最后一个数为right，之后找到中间元素的下标 mid = left + (left+right) / 2，则 mid=35，把 mid=35 与 k=40 进行比较，发现 mid
所以可以判定如果数组中有 40 这个关键字，就一定存在于 mid 和 right 指向的区域中间。
再次遍历时需要更新 left 和 mid 的位置，令 left 移动到 mid 的下一个位置上（也就是 mid+1 的位置上），同时令 mid 重新指向 left 和 right 的中间位置。如图 2 所示：
同样，用 mid 同 k 作比较，67 < 40，所以可以判定 40 如果存在，肯定处于 left 和 mid 指向的区域中。所以令 right 指向 mid 位置左侧的一个位置上(也就是 mid-1 的位置上)，同时更新 mid 的位置，如图3：
同样，用 mid 同 k 作比较，36 > 40，所以可以判定 40 如果存在，肯定处于 mid 和 right 指向的区域中。所以令 left 指向 mid 位置右侧的一个位置上（也就是 mid+1 的位置上），同时更新 mid 的位置，如图4：
当第4次做判断时，发现 mid 就是关键字 21 ，查找结束
注意：在做查找的过程中，如果 left 和 right 的中间位置在计算时位于两个关键字中间，即求得 mid 的位置不是整数，需要统一做取整操作。
3.代码如下
1.#include<stdio.h> int main() { int arr[] = { 5,12,15,19,22,35,36,40,67,78,82 }; int k; scanf("%d", &k); int sz = sizeof(arr) / sizeof(arr[0]);//求数组长度 int left = 0;//第一位数 int right = sz - 1;//最后一位数 while (left <= right) { int mid = left + (right - left) / 2; if (arr[mid] < k)//去掉左边的数组 { left = mid + 1; } else if (arr[mid] > k)//去掉右边的数组 { right = mid - 1; } else { printf("找到该数,下标是：%d\n", mid); break; } } if (left > right) { printf("找不到该数\n"); } return 0; }
4.总结
通过比较折半查找的平均查找长度，同顺序查找相对比，明显折半查找的效率要高。但是折半查找算法只适用于有序表，同时仅限于查找表用顺序存储结构表示。
最后，文章到此结束啦！
