前言
对于线性存储结构，往往需要查找某个值，如果从头找到尾，那未免有些浪费时间。我们可以简单举个例子：
让你从0-100猜一个我选中的数字，第一感觉肯定是猜一个接近50左右的，因为这样猜的话即使猜错了，那么可以直接知道要猜的数就在其中的一半(0-50或者50-100)，接着继续按这种思路下去，很快就能猜出数字。
这就是二分查找，也叫折半查找。相对于枚举查找，效率快了不少。当然，这种查找有一个前提，就是要求线性表必须是采用顺序存储结构，而且表中元素按关键字有序排列。因此在非递减顺序排列的数组中常常用到。
查找过程
首先， 假设表中元素是按升序排列，将表中间位置 记录的关键字与查找关键字比较， 如果两者相等 则查找成功； 否则利用中间位置记录将表分成前、 后两个子表， 如果中间位置记录的关键字大于查找 关键字， 则进一步查找前一子表， 否则进一步查找 后一子表。重复以上过程， 直到找到满足条件的记 录， 使查找成功， 或直到子表不存在为止，此时查 找不成功。
下面通过题目来进一步认识二分查找。
习题
NO.1 二分查找
例如
思路
首先定位最左边的元素和最右边的元素，利用利用它们的下标找出中间下标mid， 利用mid元素值和target比较，根据大小判断target在[left,mid]上还是在 [mid,right]上，按照这种思想不断缩进区间，使目标值和区间中间值相等即可。
代码
int search(int* nums, int numsSize, int target){ int left=0,right=numsSize-1; //left和right均为下标 while(left<=right) { int mid=(left+right)/2; if(nums[mid]==target) { return mid; } else if(nums[mid]<target) { left=mid+1; } else{ right=mid-1; } } return -1;
在缩进过程中，需要注意的是区间是开区间还是闭区间，换句话说就是注意mid这个元素要不要取到，倘若不要取到可以直接跳过。还有mid求出是非整数时，会按照整型类型处理，也就是中间有两个数，按左边那个数来做mid。这就是二分查找最基本的思想。利用这个思想，可以解决查找的相关问题。
NO.2 搜索插入位置
例如
思路
如果数组中存在target，那么解题思路和上一题一样，但这道题可以说就是上 道题的进阶版，不存在的话就会占用其中的元素下标。就按例2来说，先折半 一次，[1,3,5]或者[1,3]，这时就要确认mid要或不要，在这里其实都可以，如 果mid值不要，需要用一个数来记录mid元素值，最后返回记录的值即可。 而要mid值的，就是压缩到一个元素，最后返回该元素下标即可。
代码
int searchInsert(int* nums, int numsSize, int target){ int left=0,right=numsSize-1; //如果target超过区间最大数，那么直接返回right+1 if(target>nums[right]) { return numsSize; } //在区间内 while(left<right) { int mid=(left+right)/2; if(target<nums[mid]) { right=mid; //区间[left,mid] } else if (target>nums[mid]) { left=mid+1; //区间[mid+1,right] } else { return mid; } } //将数组压缩到left==right,直接返回 return left; }
另一种写法
#include<stdio.h> int searchInsert(int* nums, int numsSize, int target){ int left=0,right=numsSize-1,ros=numsSize; while(left<=right) { int mid=(left+right)/2; if(target>nums[mid]) { left=mid+1; } else { right=mid-1; ros=mid; } } return ros; }
其实两个代码思路是一致的，target<nums[mid]时，我们不知道数组是否存在target，所以要记录下mid值。所以，确认区间是最关键的。
NO.3 两个数组间的距离值
例如
思路
这道题可以看作判断arr1元素的目标区间是否符合要求，如4目标区间 [2,6]，5的目标区间[3,7]，8的目标区间[6,10],对于arr2的元素不能在此 区间内即可，所以我们可以对arr2先排序，再利用二分查找判断是否符合 要求即可。
代码
int cmp(const void *a,const void *b) { return *(int*)a>*(int*)b; } int findTheDistanceValue(int* arr1, int arr1Size, int* arr2, int arr2Size, int d){ //k记录距离值 int k=0; //快排arr2数组 qsort(arr2,arr2Size,sizeof(int),cmp); //对arr1的每个元素进行遍历 for(int i=0;i<arr1Size;i++) { //arr2的左右下标 int left=0,right=arr2Size-1; while(left<=right) { int mid=(right+left)/2; //锁定arr1元素目标区间 if(arr2[mid]>=arr1[i]-d&&arr2[mid]<=arr1[i]+d) { break; } //arr[mid]大于区间右边，说明arr2右半边的符合要求，right左移 else if(arr2[mid]>arr1[i]+d) { right=mid-1; } //arr[mid]小于区间左边，说明arr2左半边的符合要求，left右移 else if(arr2[mid]<arr1[i]-d) { left=mid+1; } } //符合要求表明left>right if(left>right) { k++; } } return k; }
NO.4 排列硬币
例如
思路
第一眼看起来，会感到这种题与二分查找无关，那我们就想n与层数的关系 ，倘若一层一层列出就是1，2，3，4...，可以看到这是一个等差数列，那 我们可以列出这样一个关系式n=k(k+1)/2;层数只能小于等于n，没办法大于n， 所以可以通过利用关系式和二分查找找出行数为多少。
代码
int arrangeCoins(int n){ int left=1,right=n; while(left<right) { long long mid=((long long)right+left+1)/2; if(mid*(mid+1)<(long long)n*2) { //区间[mid,right] left=mid; } else if(mid*(mid+1)>(long long)n*2) { //区间[left,mid-1] right=mid-1; } else { left=mid; break; } } return left; }
在解题过程中，会发现，left靠右时，mid是要包含的，如
n在区间[3,6)(即第三层没有满)中,返回值是2，即
(mid*(mid+1)>(long long)n*2）
有一种情况是mid层数有硬币但没排满，所以直接跳过mid，但这样在运行过程中，如果只剩下两个值，mid会在left上，此时会陷入死循环，所以要保证mid和left是不相同的。所以让mid位于right位置即可，所以在求mid时， (left+right)中加1即可。
总结
对于二分查找，最重要的就是确定缩减区间，接着就是确认mid是偏左的还是偏右的，倘若没有排序，条件允许情况下要想排序。
今天这篇文章是比较简单的，当你熟悉二分查找时，其实是非常简单的。
希望我的理解对你有所帮助，感谢你的观看。
