【二分查找专题】给出四种二分查找的模版
本问题对应课程链接：剑指offer刷题第四期
本次打卡的任务很简单，就是给出四种变形二分查找的模版代码，并且给出了对应的方法名字。
比如对于一个有序数组
arr = [1，2，3，3，3，4，5，5，7]，target = 3，那么
1.寻找第一个大于 target 的元素的下标，本案例中4 就是第一个大于 target 的元素 ，下标 = 5。
对应方法名格式为
int upper(int[] arr, int target){
//如果都不存在，则返回-1
}
2.如果数组中存在元素等于 target，则返回最后一个等于target 的元素下标，如果不存在，则返回第一个大于 target 的元素下标。本案例中最后一个等于target的下标 = 4。
对应方法名
int floor_upper(int[] arr, int target){
//如果都不存在，则返回-1
}
3.寻找最后一个小于 target 的元素的下标，本案例中 2 则是最后一个小于 target 的，下标 = 1.
对应方法名格式为
int lower(int[] arr, int target){
//如果都不存在，则返回-1
}
4.如果数组中存在元素等于 target，则返回第一个等于target 的下标，如果不存在，则返回最后一个小于 target 的元素的下标。本案例中第一个等于target的下标 = 2。
对应方法名格式为
int floor_lower(int[] arr, int target){
//如果都不存在，则返回-1
}
注意：大家给了模版之后，选择一个适合自己的模版，以后都用这个模版，忘了怎么办？这玩意的区别就是要么是大于，要么是大于等于，你如果记混了，可以随便找一组数据试一下，就能分辨出来了，我笔试时都这样干，，，
答案来了，具体答案看这篇文章：4种二分查找模版讲解
shuaidi
共以下 17 个回答
/*本次打卡的任务很简单，就是给出四种变形二分查找的模版代码，并且给出了对应的方法名字。
比如对于一个有序数组
arr = [1，2，3，3，3，4，5，5，7]，target = 3，那么
*/
/*1.寻找第一个大于 target 的元素的下标，本案例中4 就是第一个大于 target 的元素 ，下标 = 5。
对应方法名格式为
int upper(int[] arr, int target){
//如果都不存在，则返回-1 arr, int target){
}
*/
int upper(vector
int len = arr.size();
int left = 0, right = len – 1;
}
/*2.如果数组中存在元素等于 target，则返回最后一个等于target 的元素下标，如果不存在，则返回第一个大于 target 的元素下标。本案例中最后一个等于target的下标 = 4。
对应方法名
int floor_upper(int[] arr, int target){
//如果都不存在，则返回-1
}
*/
int floor_upper(vector arr, int target){
int len = arr.size();
int left = 0, right = len – 1;
}
/*3.寻找最后一个小于 target 的元素的下标，本案例中 2 则是最后一个小于 target 的，下标 = 1.
对应方法名格式为
int lower(int[] arr, int target){
//如果都不存在，则返回-1
}
*/
int lower(vector arr, int target){
int len = arr.size();
int left = 0, right = len – 1;
}
/*4.如果数组中存在元素等于 target，则返回第一个等于target 的下标，如果不存在，则返回最后一个小于 target 的元素的下标。本案例中第一个等于target的下标 = 2。
对应方法名格式为
int floor_lower(int[] arr, int target){
//如果都不存在，则返回-1
}*/
int lower(vector arr, int target){
int len = arr.size();
int left = 0, right = len – 1;
}
打卡
”’java
//寻找第一个大于target的元素
int upper(int[] arr,int target){
//如果都不存在，则返回-1
int l = 0;
int r = arr.length – 1;
if(arr[r] <= target){
return -1;
}
while(l < r){
int mid = (l + r)/2;
if(arr[mid] <= target){
l = mid + 1;
}else{
r = mid;
}
}
return l;
}
//返回最后一个等于target的元素下标,否则返回第一个大于target的元素
int floor_upper(int[] arr,int target){
//如果都不存在，则返回-1
int l = 0;
int r = arr.length – 1;
if(arr[r] < target){
return -1;
}
while(l < r){
int mid = (l + r)/2;
if(arr[mid] <= target){
l = mid + 1;
}else{
r = mid;
}
}
if(l-1 >= 0 && arr[l-1] target){
return l – 1;
}
return l;
}
//寻找最后一个小于target的元素的下标
int lower(int[] arr,int target){
int l = 0;
int r = arr.length – 1;
if(arr[l] >= target){
return -1;
}
while(l < r){
int mid = (l+r+1)/2;
if(arr[mid] < target){
l = mid;
}else{
r = mid – 1;
}
}
return l;
}
//返回第一个等于target的元素下标，若不存在则返回最后一个小于target元素的下标
int floor_lower(int[] arr,int target){
int l = 0;
int r = arr.length – 1;
if(arr[l] > target){
return -1;
}
while(l < r){
int mid = (l + r + 1)/2;
if(arr[mid] < target){
l = mid;
}else{
r = mid – 1;
}
}
if(l+1 < arr.length && arr[l+1]target){
return l+1;
}
return l;
}
”’
c++ 模版主要是界限
二分查找
代码
二分主要还是边界太恶心了
“`c++
#include
#include
using namespace std;
const int N = 1e5 + 10;
int n,m;
int q[N];
int main() {
cin >> n >> m;
for(int i = 0; i < n; i ++ ) scanf(“%d”,&q[i]);
while(m–) {
int x;
cin >> x;
int l = 0, r = n – 1;
while(l < r) {
int mid = (l + r) >> 1;
if(q[mid] > x) {
r = mid ;
}else if (q[mid] x) {
r = mid;
} else {
l = mid + 1;
}
}
if(q[l] != x) {
cout << “-1 -1” << endl;
} else {
cout << l <<‘ ‘;
r = n-1;
while(l < r) {
int mid = (l + r + 1) >> 1;
if(q[mid] < x) {
l = mid;
} else if (q[mid] x) {
l = mid;
} else {
r = mid -1;
}
}
cout << l << endl;
}
}
}
“`
#include
#include
using namespace std;
int upper(vector arr,int target){
int l = 0;
int r = arr.size()-1;
if(arr[r] <= target){
return -1;
}
while(l < r){
int mid = (r – l) / 2 + l;
if(arr[mid] > target){
r = mid;
}
else if(arr[mid] target){
l = mid + 1;
}
else{//arr[mid] < target
l = mid + 1;
}
}
} arr,int target){ arr,int target){
//2.如果数组中存在元素等于 target，则返回最后一个等于target 的元素下标，
// 如果不存在，则返回第一个大于 target 的元素下标
int floor_upper(vector
int l = 0;
int r = arr.size()-1;
if(arr[r] < target){
return -1;
}
while(l < r){
int mid = (r – l) / 2 + l;
if(arr[mid] > target){
r = mid;
}
else if(arr[mid] target){
l = mid + 1;
}
else{//arr[mid] < target
l = mid + 1;
}
}
if(l – 1 >= 0 && arr[l-1] target){
return l – 1;
}
return l;
}
//3.寻找最后一个小于 target 的元素的下标
int lower(vector
int l = 0;
int r = arr.size()-1;
if(arr[l] >= target){
return -1;
}
while(l < r){
int mid = (r – l + 1) / 2 + l;
if(arr[mid] > target){
r = mid – 1;
}
else if(arr[mid] target){
l = mid – 1;
}
else{//arr[mid] < target
l = mid;
}
}
} arr,int target){
// 4.如果数组中存在元素等于 target，则返回第一个等于target 的下标，
// 如果不存在，则返回最后一个小于 target 的元素的下标
int floor_lower(vector
int l = 0;
int r = arr.size()-1;
if(arr[l] >= target){
return -1;
}
while(l < r){
int mid = (r – l + 1) / 2 + l;
if(arr[mid] > target){
r = mid – 1;
}
else if(arr[mid] target){
l = mid – 1;
}
else{//arr[mid] < target
l = mid;
}
}
if(l + 1 < arr.size() && arr[l+1] target){
return l – 1;
}
return l;
}
写二分，注意遵循 循环不变量 原则，即定义了一套边界标准，无论是左闭右闭，还是左闭右开之后，就不再变化。