二分查找及变体（迭代实现）
二分查找
-
介绍：
二分查找又称折半查找，顾名思义，就是将有序序列进行折半，分成两个区间，如果目标值比中间那个数大，又由于序列有有序的，那么目标值肯定比左半区间所有的数都大，就只需要在右半区间进行查找。 -
例子：
给定有序序列[1,2,3,4,5],设定目标值为4，将该序列分成两个区间，中间值为3,而4比3大，就在[4,5]这个区间进行查找，重复该操作，直至找到目标值或者达到边界结束操作。
3.算法要求：
- 必须用顺序存储结构；
- 被查找的序列必须是有序的。
查找目标值下标的二分查找
代码：
int binary_search(int arr[], int left, int right, int target){ //这里left和right分别代表搜索区间边界 //即搜索区间为[left,right] /*如何确定循环结束条件： 假设为left<right，那循环结束时就是left=right， 即[right,right],明显下标为right的这个值没有进行检测，漏掉了可疑选项 --------------------------------------------------------------- 当结束条件为left<=right时，那循环结束条件就为left=right+1， 即[right+1,right],边界值right被检索到 --------------------------------------------------------------- 当right取数组长度时通过类似的思路同样可以确定循环结束条件， 别漏掉潜在答案就行*/ while (left> 1; //找到就返回下标 if (arr[mid] == target) return mid;//中间值比目标值大 //搜索区间为左半区间 else if (arr[mid] > target) right = mid - 1;//中间值比目标值小 //搜索区间为右半区间 else left = mid + 1; } //没找到返回-1 return -1;}查找大于等于目标值的第一个元素的下标二分查找
–上述二分查找有一个小瑕疵，如果目标值有多个怎么办？想知道有多少个，并且返回它们的下标集合怎么做呢？当然可以往左右两边进行线性探测，这里我们先找大于等于目标值的第一个元素的下标，至于为什么咱们最后来研究研究。
int lower_bound(int arr[], int left, int right,int target){ //搜索区间为[left,right] int high = right;//后面解释为什么记录右边界的值 while (left> 1; //我们的目的是找到第一个大于等于目标值的元素的下标 //如果找到与目标值相等的元素 //就需要往左边压缩区间 //比如[1,2,2,2,3],第一个找到最中间那个2 //继续往左区间检索就能找到第一个2 if (arr[index]==target) right = --index; //中间值比目标值大 //在左半区间进行检索 else if(arr[index]>target) right = --index; //中间值比目标值大 //在右半区间进行检索 else left = ++index; } /*可以对上述代码进行缩短，第一个和第二个条件成立后 执行的语句是一样的，可以合并*/ /*left的取值范围为[left，right+1]， 如果left取到了right+1，说明没有大于等于目标值的元素, 而right已经发生了改变，所以开始的时候用一个变量来记录； 如果left取到了搜索区间内的下标，我们不能确定该下标对应 的元素是否等于目标值，因为我们找的是大于等于目标值的元素， 需要判断是否等于目标值*/ if (left == high + 1 || arr[left] != target) return -1; return left;}查找严格大于目标值的第一个元素的下标的二分查找
–解释一下什么是严格大于，其实就是大于，不同于大于等于，3>2这个就是严格大于。
{ //搜索区间为[left,right] int high = right; while (left > 1; //当前值比目标值大，就在左半区间进行检索 if (arr[index] > target) right = --index; /*我们的目标是找到第一个严格大于目标值的元素的下标，如果找到与目标值相等的元素，就往右压缩区间。-----------------------------------------比如：[1,2,2,2,3,4,5],目标值为2，第一次锁定中间位置那个2，继续往右压缩，找到3，也就是第一个严格大于2的元素。-----------------------------------------这里将arr[index]==target和arr[index]<target进行了合并*/ else left = ++index; } /*同样地，left的取值范围为[left,right+1], 如果取到right+1，说明该序列没有一个元素比 目标值大；如果取到0，说明该序列所有元素都 比目标值大；上面两种情况就说明该序列里面 不包含目标值*/ if (left == 0 || left == high + 1) return -1; else return left;}这个时候来解决先前提出的问题，我们可以通过上述两种二分变体找到第一个大于等于目标值的元素的下标和第一个严格大于目标值的元素的下标，两个下标进行相减就知道该序列里面有个多少个目标值；而这个下标组成的区间（左闭右开）就是目标值的下标值。
总结：
- 注意二分查找循环结束时的条件,是如何进行分析
- 理解二分查找变体的思路