1389 蓝桥杯 二分查找数组元素 简单
//C++风格解法1，lower_bound(),通过率100%
//利用二分查找的方法在有序的数组中查找，左闭右开
#include <bits/stdc++.h>
using namespace std;int main(){int data[200];for(int i = 0 ; i < 200 ; ++i) data[i] = 4 * i + 6;int tager; cin >> tager; //输入目标值cout << lower_bound(data,data + 200,tager) - data;return 0;
}在有序数组中进行二分查找，升序，查找第一个 >= target的元素，时间复杂度O(logn)
lower_bound(data,data + 200,tager)返回物理地址，减去首地址得到下标
// 升序数组中：
upper_bound(a.begin(), a.end(), x); // 查找第一个 > x的元素
lower_bound(a.begin(), a.end(), x); // 查找第一个 >= x的元素
// 降序数组中：
upper_bound(a.begin(), a.end(), x, greater<type>()); // 查找第一个 < x的元素
lower_bound(a.begin(), a.end(), x, greater<type>()); // 查找第一个 <= x的元素排序的时候，默认是从小到大，但是第三个参数用greater会变成从大到小，而不需要cmp
upper_bound默认是找大于，但是第三个参数用greater就是找小于，lower_bound同理可得
//C风格解法2，逆推，虽然用了cin、cout，通过率100%
#include <iostream>
using namespace std;
int main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int x;cin >> x;cout << (x - 6) / 4 << endl;return 0;
}//C风格解法3，二分法左闭右开
#include <iostream>
using namespace std;int main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int x;cin >> x;int data[200];for(int i = 0 ; i < 200 ; i ++)data[i] = 4 * i + 6;int left = 0,right = 200; //定义target在左闭右开的区间里，即[left, right)//right指向最后一个元素的后一个元素while(left < right){ //如果一开始left = right，target在[left, right)区间上无意义int mid = left + ((right - left) >> 1); //等同于 (left + right) / 2，防止溢出if(data[mid] >= x)right = mid; //target在左区间[left, mid] else left = mid + 1; //target在右区间[left, right) } cout << left << endl; //left = rightreturn 0;
}基于此方法改动可能会超时，
如传统三段式if、else if、else，二分法左闭右闭，while(left <= right)等
right = left时，循环条件被修改成 while (left <= right) 会接着做循环
出错，如data[mid] > x，注意返回的不是mid
出错，声明mid，输出mid
如果是左闭右闭，left = 0，right = 199， while (left <= right)
定义了target在左闭右闭的区间内，[left, right]，right指向最后一个元素
left = right时，target在区间[left, right]仍然有效
若循环条件修改为while (left < right)，nums[middle] = A 时< target = B，
此时 left = mid + 1，left = right，而循环条件为while (left < right)，
还未找到A 的情况下算法就跳出了循环
reference:
彻底记住 lower_bound 和 upper_bound 功能和用法_lower_bound和upper_bound的用法-CSDN博客
关于lower_bound( )和upper_bound( )的常见用法_lowerbound和upperbound-CSDN博客
lower_bound, upper_bound, greater, less 用法_lower_bound greater-CSDN博客
【二分查找】详细图解_二分查找法流程图-CSDN博客
图文并茂带你入门二分查找算法 - 知乎 (zhihu.com)
