引入：
二分法是一个非常高效的算法，它常常用于计算机的查找过程中。
先玩一个小游戏。预先给定一个小于100的正整数x，让你猜，猜测过程中给予大小判断的提示，问你怎样快速地猜出来？
这样猜测最快，先猜50，如果猜对了，结束；如果猜大了，往小的方向猜，再猜25；如果猜小了，往大的方向猜，再猜75；…，每猜测1次就去掉一半的数，就这样可以逐步逼近预先给定的数字。这种思想就是二分法。
概念：
在用二分法进行查找时，查找对象的数组必须是有序的，即各数组元素的次序是按其值的大小顺序存储的。其基本思想是先确定待查数据的范围（可用 [left,right] 区间表示），然后逐步缩小范围直到找到或找不到该记录为止。具体做法是：
先取数组中间位置（mid=(left+right)/2）的数据元素与给定值比较。若相等，则查找成功；
否则，若给定值比该数据元素的值小（或大），则给定值必在数组的前半部分[left,mid-1]（或后半部分[mid+1,right]），然后在新的查找范围内进行同样的查找。
如此反复进行，直到找到数组元素值与给定值相等的元素或确定数组中没有待查找的数据为止。
因此，二分查找每查找一次，或成功，或使查找数组中元素的个数减少一半，当查找数组中不再有数据元素时，查找失败。
二分法查找的时间复杂度O(logn)。
二分法的适用情况一般满足以下几点：
（1）该数组数据量巨大，需要对处理的时间复杂度进行优化；
（2）该数组已经排序；
（3）一般要求找到的是某一个值或一个位置。
设一有序的数组中有11个数据元素，它们的值依次为
{3，8，15，21，35，54，63，79，82，92，97}，
用二分查找在该数组中查找值为82和87的元素的过程。
实现算法：
int binarySearch(int *nums,int numsSize,int target)//nums 数组 numsSize 数组长度
//target 目标值
{
int left=0;
int right = numsSize-1; //注意
while(left<=right) //注意
{
int mid = left +(right-left)/2;
if(nums[mid] == target)
return mid;
else if(nums[mid]<target)
{
left = mid+1; //注意
}
else if(nums[mid]>target)
{
right = mid-1; //注意
}
}
return -1;
}
int nums[200];
int main(){
int n,t;
cin>>n;
for(int i=0;i<n;i++){
cin>>nums[i];
}
cin>>t;
int ans =binarySearch(nums,n,t);
}
返回第一次出现位置的二分查找
int lower_bound(int *nums,int numsSize,int target)
{
int left=0,right=numsSize-1,ans=numsSize;
while(left<=right)
{
int mid = left+(right-left)/2;
if(nums[mid]>=target)
{
right = mid-1;
ans = mid;
}
else
{
left = mid+1;
}
}
return ans;
}
查找左侧边界的数，即在一个有序数组中，找到第一个等于target的下标。比如数组int nums[]={5,7,7,8,8,8,10}，target=8，第一个等于8的下标是3，第一个大于等于8的数组下标也是3。即找到第一个等于target的数等价于 找第一个小于等于target的数的下标，然后我们判断该下标所对应的数是否是target。
返回最后一次出现位置的二分查找
int high_bound(int numsSize,int target)
{
int left=0,right=numsSize-1,ans=numsSize;
while(left<=right)
{
int mid = left+(right-left)/2;
if(nums[mid]>target)
{
right = mid-1;
ans = mid;
}
else
{
left = mid+1;
}
}
return ans;
}
寻找右侧边界的数，就是找第一个大于target的数，返回其下标减1，int nums[]={5,7,7,8,8,8,10}，最后一个等于8的下标是5，第一个大于8的数是10，其下标是6，减去1是5，找target最后位置等价于找第一个大于target的下标减1，然后判断该位置上的数是否等于target。
STL模板
binary_search
binary_search：查找某个元素是否出现。
函数模板：binary_search(arr[],arr[]+size , indx)；
参数说明：
arr[]： 数组首地址
size：数组元素个数
indx:需要查找的值
函数功能： 在数组中以二分法检索的方式查找，若在数组(要求数组元素非递减)中查找到indx元素则真，若查找不到则返回值为假。
int a[100]= {4,10,11,30,69,70,96,100};
int b=binary_search(a,a+9,4);//查找成功，返回1
lower_bound
lower_bound( begin,end,num)：
从数组的begin位置到end-1位置二分查找第一个大于或等于num的数字，找到返回该数字的地址，不存在则返回end。通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。
注意因为返回值是一个指针，所以减去数组的指针就是int变量了
upper_bound
upper_bound( begin,end,num)：
从数组的begin位置到end-1位置二分查找第一个大于num的数字，找到返回该数字的地址，不存在则返回end。通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。
int num[10]={1,2,4,7,7,7,7,15,34};
sort(num,num+9); //按从小到大排序
int pos1=lower_bound(num,num+9,7)-num; //返回数组中第一个大于或等于被查数的值 在数组num中的下标位置
int pos2=upper_bound(num,num+9,7)-num; //返回数组中第一个大于被查数的值 在数组num中的下标位置
cout<<pos1<<" "<<num[pos1]<<endl;
cout<<pos2<<" "<<num[pos2]<<endl;
二分答案
木材厂有一些原木，现在想把这些木头切割成一些长度相同的小段木头（木头有可能有剩余），需要得到的小段的数目是事先给定的，切割时希望得到的小段越长越好。
编写程序，输入原木的数目 N 和需要得到的小段的数目 K以及各段原木的长度，计算能够得到的小段木头的最大长度。
木头长度的单位是 cm。原木的长度都是正整数，要求切割得到的小段木头的长度也是正整数。
例如，输入原木的数目 N 和需要得到的小段的数目 K 分别为3和8，输入的3段原木的长度分别为124、224和319，则能够切割得到的小段的最大长度为 74。
评论区