1389 蓝桥杯 二分查找数组元素 简单

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 = right
  return 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)