最初，在规则的数列中寻找给定的要素时，通常采用循环扫描的方法。 时间复杂度为o(n )，空间复杂度为o )1)。 例如，在有序的数列{ 1，2，3，4，5 }中，寻找要素值为3的位置，下标从0开始遍历所有数值，在要素值为3时返回要素的下标。
但是，由于该方法在时间上比较复杂，所以在这种情况下引入了二分搜索的思想，设置了左边距left、右边距right、中间要素的下标mid，通过比较mid和目标值的大小来改变区间。
1 .查找指定元素的下标：
如果数组num [8]={ 1，2，2，2，3，4，5，6 }
查找数值为4的下标。
# includeiostreamusingnamespacestd； intbinary_search(intnum[]，int target ) { int left=0，right=7； 在left right中无法构成闭区间，可以容许left==right，否则在数组长为1的情况下，无法通过二分法检测数组内的内容while (left right )//寻找中间点的下标保持原样) ELSEif(num[mid]target ) right=mid - 1； else return mid； //找不到目标值时，输出-1 return -1； }int main () intnum(8)={ 1，2，2，2，3，4，5，6 }； int target=4； intindex=binary_search(num，target )； 计数索引； }最终输出下标： 5
符合要求。
2 .查找数列第一个目标值以上元素的下标：
如果数组num [8]={ 1，2，2，2，3，4，5，6 }
查找目标值大于或等于2的第一个元素的下标。
方法1 :直接使用二分法
# includeiostreamusingnamespacestd； intbinary_search(intnum[]，int target ) { int left=0，right=7； left=right时，脱离循环，最后出发的位置时，寻找目标所在的位置或者目标所在的位置while(left right )//中间点的下标，直接使用leftright )/2的话，数值会变大小于此目标的值不是答案，因此搜索范围内的if [ mid ]目标(left=mid 1； //因为首先要查找target以上的值，所以该target以上的值可能是答案，所以在检索范围内输入elseif(num[mid]target ) right=mid； //要寻找的最初的target以上的值，因为与该target相等的数值可能是答案，所以应该留在检索范围内的else right=mid； }返回左； }int main () intnum(8)={ 1，2，2，2，3，4，5，6 }； int target=2； intindex=binary_search(num，target )； 计数索引； }最终输出下标： 1
符合要求。
方法可以调用algorithm库下的lower_bound ()函数
调用格式：
lower_bound (数组开头地址、数组末尾地址、找到的数字) ) ) ) )。
返回值是要搜索数字的地址。
具体代码如下。
# include iostream # includealgorithmusingnamespacestd； int main () intnum(8)={ 1，2，2，2，3，4，5，6 }； int target=2； intindex=lower_bound(num，num 8，2 )- num； 计数索引； }最终输出下标： 1
符合要求。
时间的复杂性也是o(logn )
3 .查找大于数列第一个目标值的元素下标：
如果数组num [8]={ 1，2，2，2，3，4，5，6 }
查找目标值大于2的第一个元素的下标。
br> 方法1：直接使用二分法 #include <iostream>using namespace std;int Binary_Search(int num[],int target){ int left = 0, right = 7; //当left = right时，退出循环，最后得出的位置时，目标所在的位置，或者是目标应该存在的位置 while(left < right){ //寻找中间点的下标，如果直接用(left + right)/2，当数值较大时容易造成数值溢出 int mid = left + ((right - left)>>1); //因为要寻找的第一个大于target的值，这个小于target的数值不可能是答案，所以应当移除在搜索范围之内 if(num[mid] < target) left = mid + 1; //因为要寻找的第一个大于target的值，这个大于target的数值可能是答案，所以应当保留在搜索范围之内 else if(num[mid] > target) right = mid; //因为要寻找的第一个大于target的值，这个等于target的数值不可能是答案，所以应当移除在搜索范围之内 else left = mid + 1; } return left;}int main(){ int num[8] = {1,2,2,2,3,4,5,6}; int target = 2; int index = Binary_Search(num, target); cout<<index;}最后输出下标：4
符合要求。
方法2.可以调用algorithm库下的upper_bound()函数
调用格式:
upper_bound(数组首地址，数组末尾地址，查找的数字)
返回值为查找数字的地址。
具体的代码如下：
最后输出下标：4
符合要求。
时间复杂度也为O(logn)
4.寻找数列中最后一个等于或小于目标值的元素的下标：
对于数组num[8] = {1,2,2,2,3,4,5,6}
查找最后一个小于或等于目标值为2的元素下标。
最后输出下标：3
符合要求。
5.寻找数列中最后一个小于目标值的元素的下标：
对于数组num[8] = {1,2,2,2,3,4,5,6}
查找最后一个小于目标值为2的元素下标。
最后输出下标：0
符合要求。
总结：
上述的代码是针对左开右闭的情况，来进行区间的变化。对于最后一个小于或等于x的情况，要对于mid值的选择要取高位，否则会陷入死循环。
涉及的题目
1.寻找最大情况的最小值：
分配给商店的最多商品的最小值
爱吃香蕉的珂珂
2.寻找最后一个小于等于当前值的数
在线选举