蓝桥杯省赛无忧 竞赛常用库函数 课件7 二分查找

01 二分查找的前提

02 binary_search函数

#include<bits/stdc++.h>
using namespace std;
int main(){
	vector<int> numbers={1,3,5,7,9};
	int target = 5;
	//使用binary_search 查找目标元素
	bool found = binary_search(numbers.begin(),numbers.end(),target);
	if(found){
		cout<<"Target element"<< target<<" found."<<endl;
	}else{ 
		cout<<"Target element"<<target<<" not found."<<endl;
	}
	return 0;
}

03 lower_bound和upper_bound函数

#include<bits/stdc++.h>
using namespace std;
int main(){
	vector<int> v={5,1,7,3,10,18,9};
	sort(v.begin(),v.end());
	for(auto&i:v)cout<<i<<' ';
	cout<<'\n';
	//找到数组中第一个大于等于8的元素的位置
	cout<<(lower_bound(v.begin(),v.end(),8)-v.begin())<<'\n'; 
	return 0;
}

04 例题讲解

https://www.lanqiao.cn/problems/1389/learning/?page=1&first_category_id=1&problem_id=1389

#include <iostream>
using namespace std;
int main()
{
  int i;
  int data[200];
  for(i=0;i<200;i++)data[i]=4*i+6;
  int target;
  cin>>target;
  for(i=0;i<200;i++){
    if(target==data[i]){
      cout<<i;
      break;
    }
  }
  return 0;
}