学习二分查找

一，什么是二分查找？

二分查找是一种在有序数组中快速查找目标值的算法。

核心思想：就是每次把查找的区间减半，用中间值判断目标值再左还是在右，然后不断缩小区间范围。

前提条件：数组必须有序，（注：升序降序都行）

二，关于二分查找的时间复杂度

时间复杂度：O（log n） 注：比暴力O(n)快得多，且数据越大越明显。

空间复杂度：O（1）（非递归）

三，主要的二分模版

#include<iostream> #include<algorithm> using namespace std; int a[100010]={0}; int main(){ int n,m; cin>>n>>m; for(int i=1;i<=n;i++){ cin>>a[i]; } sort(a+1,a+n+1); int x; while(m--){ cin>>x; int left=1; int right=n; int mid; bool tot=false; while(left<=right){ mid=left+(right-left)/2; if(x==a[mid]){ tot=true; break; }else if(x<a[mid]){ right=mid-1; }else if(x>a[mid]){ left=mid+1; } } if(tot==true){ cout<<"YES"<<'\n'; }else{ cout<<"NO"<<'\n'; } } return 0; }

有些关键点：

1，mid=left+(right-left)/2；会比(right+left)/2；更安全，防止int数据类型溢出。

2，就是循环条件：left<=right。

情况一：当然循环条件可以有选择的使用，常用的是小于等于是为了方便：查找目标值是否存在。查找区间也是[left,right]。

逻辑：当left=right时，区间里还有最后一个元素需要检查，此时如果不检查就会漏掉这个元素。

情况二：这个情况也是特殊情况，应为有些题会让你找数组边界，这个时候可以用left=light，一般这样的题数组区间是左开右闭合[left,right)，不包含right；

逻辑：循环结束时left==light，返回left就是答案，或返回right。

总结：

二分查找就是：有序，减半，判断，缩边。