简介
折半查找也就是二分查找，也可以叫二分法，本质上都是一样的，通过比对中间值与目标值，一次性就能筛掉一半的数字。
举例：
一个猜数字游戏，让你来猜1-100中我选中的数，如果猜中游戏结束，如果猜的数字比选的数字大，告诉你猜的数大了，反之亦然。
如何针对上述游戏，寻找到一个最快的办法呢？—— 拼运气 或 折半查找
每次猜的数字为区间范围的中数，这样最多在 次内一定能找到！
假设选中的数字为 target = 77
第一次：选(1 + 100) / 2 = 50(这里取整数即可) -> 小了
第二次：选(50 + 100) / 2 = 75 -> 小了
第三次：选(75 + 100) / 2 = 87 -> 大了
第四次：选(75 + 87) / 2 = 81 -> 大了
第五次：选(75 + 81) / 2 = 78 -> 大了
第六次：选(75 + 78) / 2 = 76 -> 小了
第七次：选(76 + 78) / 2 = 77 -> 对了
通过上述案例，我们能发现，每次在进行查找的时候能够排除一半的错误答案！相当于对所有可能的个数除2。因此折半查找的时间复杂度 。100个数，最多只要7次就能找到！
虽然折半查找效率这么高，但也是有缺点的～互联网没有“银弹”～
折半查找最大的问题在于，要求你进行查找的数据集必须是有序的！！！所以在编程的时候，可能需要你先进行一次排序～
编码
思路：
1.如果没告诉你数组是有序的，需要对数组进行一次排序(假设是有序的)
2.计算中间数在数组的位置
3.将中间数与目标值进行比对，如果中间数小了，就去右边的区间继续查找，如果中间数大了，就去左边的区间继续查找，如果刚好相等，说明找到了，返回即可。
下述折半查找的代码是基于比区间来写的，一定需要注意！！！否则会导致最终结果不对，这是二分法的细节问题(很容易出错)！
#include <stdio.h>
int BinarySearch(const int* arr, int target, int size)
{
int left = 0;
int right = size - 1;
while (left <= right) //这里定义的是[left, right] 闭区间，一定要注意
{
//计算中间的那个元素的下标
int mid = left + (right - left) / 2;
//如果要找的数小于中间的那个数
if (target < arr[mid])
right = mid - 1;
else if (target > arr[mid])
left = mid + 1;
//如果找到了就直接返回这个元素的下标
else
return mid;
}
}
int main()
{
int arr[] = { 5,8,10,23,48,66,88,100 };
int target = 48;
//计算数组中元素个数
int size = sizeof(arr) / sizeof(arr[0]);
int index = BinarySearch(arr, target, size);
printf("找到了，这个数在数组中的下标为：%d", index);
return 0;
}优化
上述的代码是针对目标值出现在数组的情况，不适用于更普遍一半的情况。在C++标准库中就提供了折半查找这个函数，他的功能是，找到目标值在数组中第一次出现的位置，如果数组中未存在目标值，则找到插入位置。
通过观察上述折半查找算法的过程，我们会发现，
1.如果中间值arr[mid]大于目标值target，则arr[mid+1]~最后 的值都大于目标值taget。arr[left]~arr[mid]可能小于等于目标值target。
2.如果中间值arr[mid]小于目标值target，则arr[left]~arr[mid] 的值都小于目标值target。
最终我们得出，left左边的值都是小于目标值的，right右边的值都是大于目标值的。
如果要找到插入的位置，则找到第一个大于等于目标值的位置。
代码
int searchInsert(int* nums, int numsSize, int target)
{
int left = 0;
int right = target - 1;
while(left <= right)
{
int mid = left + (right -left) / 2;
if(nums[mid] < target)
left = mid + 1;
else
right = mid - 1;
}
return left;
}上述代码，将中间值大于等于的情况进行了合并。为的是找到第一个出现的位置，并且代表的含义也变了——right右边的数是大于等于目标值target的。
举个例子：
int arr[] = {1，2，3，3，3，3，5，6};
target = 3要去查找第一个3，我们的中间值第一次找到的3是第二个，但我们要找的是第一个，所以需要继续缩小右边界，才能找到。
至于最后为什么返回的是left呢？因为根据代码，left左边的值是小于目标值的，right右边的值是大于等于目标值的，而最终left和right的位置一定是满足right在left的左边且相差一个元素，于是就返回left了。
