数据结构算法二分查找研究(c++编写实例)

二分查找

什么是二分查找？

二分查找也称折半查找（Binary Search），它是一种效率较高的查找方法。但是，折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列,其实就是，对于要查找的元素，每次通过与区间的中间元素对比，不断缩小区间，直至查找到要查找的元素，或者左边大于右边（区间为0），至于什么是左边还是右边，各位看客容我慢慢道来。

二分查找的优缺点

优点：二分查找是一个常用的高效的查找算法，其时间复杂度O(logn)
我们假设给出一组数据，其大小为n,由于每次查找都会使得区间减半，所以区间长度不断的除以2，直至或者说最坏情况区间为零
总共有n个元素，
渐渐跟下去就是n,n/2,n/4,…n/2^k（接下来操作元素的剩余个数），其中k就是循环的次数
最后操作的元素最后直至为一是可以推出：n/2^k=1，即k=log2n，所以时间复杂度为O(logn)
缺点：
1.必须采用顺序存储结构。（比如数组）
2.必须按关键字大小有序排列。（数据必须有序，如果不为有序的，对于取中间元素作为比较将没有意义）
主要思想：将n个元素分成大致相等的两部分，取a[n/2]与x做比较，如果x=a[n/2],则找到x,算法中止；如果x<a[n/2],则只要在数组a的左半部分继续搜索x,如果x>a[n/2],则只要在数组a的右半部搜索x(那么左边和右边其实就是左右边界)
说了这么多，还是上代码吧

代码实现

int find(int x) { int mid; int l=1,r=n; while(l<=r) { int mid=(l+r)>>1;//与除以二等效，只是在计算机里更快，这里算mid时需要技巧防止溢出，建议写成: mid = left + (right - left) >> 2  if(a[mid]==x)//取a[n/2]与x做比较,如果x=a[n/2],则找到x return mid; else if(a[mid]>x)//如果x>a[n/2],则只要在数组a的右半部搜索x r=mid+1; else if(a[mid]<x)//如果x<a[n/2],则只要在数组a的左半部分继续搜索x l=mid+1; } return l; } 

c++中的二分查找

binary_search 返回bool值，是否存在，如果存在返回1，反之则为0
上代码

#include<iostream> #include<cstring> #include<algorithm>//一定要用到这个头文件 #define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0) #define endl '\n'  typedef long long ll; using namespace std; const int maxn=1e8+7; int a[maxn]; int main() { int x; cin>>x; for(int i=1;i<=5;i++) cin>>a[i]; cout<<binary_search(a+1,a+6,x)<<endl;//a表示首地址，即a[0]，a+1,a+6表示从a[1]到a[6]这个区间查找是否有x这以元素 return 0; } 

lower_bound 返回可插入的最小位置的迭代器，即返回第一个符合条件的元素位置，一般符合的条件为第一个大于等于某个元素的位置

#include<iostream> #include<cstring> #include<algorithm> #define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0) #define endl '\n'  typedef long long ll; using namespace std; const int maxn=1e8+7; int a[maxn]; int main() { int x; cin>>x; for(int i=0;i<5;i++) cin>>a[i]; cout<<lower_bound(a,a+5,x)-a<<endl;//返回的是位置，一般我们找的是在数组中的第几个位置，所以通常是减去首地址，即a[0]/a; return 0; } 

upper_bound 返回可插入的最大位置的迭代器，即返回最后一个符合条件的元素的位置，，一般符合的条件为最后一个大于等于某个元素的位置，代码实现如上
附赠查找第一个大于等于x和最后一个大于等于x的位置的代码

int find_low(int x) { int mid,l,r=n; while(l<=r) { mid=(l+r)>>1; if(a[mid]<x) l=mid+1; else r=mid-1; } return l; } int find_up(int x) { int mid,l=1,r=n; while(l<=r) { mid=(l+r)>>1; if(a[mid]<=x) l=mid+1; else r=mid-1; } return l; } 

最最最后推荐一个大佬的博客讲的巨详细

本文地址：https://blog.csdn.net/qq_45995244/article/details/107730296