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

2024-01-08 10:30:20

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)

文章来源:https://blog.csdn.net/F87523399332578_/article/details/135385916
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。