【算法】二分查找

x33g5p2x  于2021-12-19 转载在 其他  
字(0.9k)|赞(0)|评价(0)|浏览(166)

如果我们已知一些有序的数字,在其中需要查找给定的数字,如何解决这个问题?
最简单的方法是挨个查找,使用循环,O(n)的复杂度。

int a[]={1,2,5,6,9,12,35,60,89,125};
int k=89;
for(int i=0;i<10;i++){
  if(a[i]==k){
    cout<<i<<endl;
    return 0;
  }
}
cout<<"Not found.";

输出:8

但是当数据比较多的时候,这种查找方法的效率很底下。如果数据是有序的,我们可以使用二分查找的方法来实现。
例如,在这10个数中,我们先从中间开始查找,最中间的数是9,我们把9和待查找的89对比后,发现9<89,意味着9以及它左边的数都小于89,因此一半的区间就可以舍去了。
然后,剩余的五个数字中,我们再次查找中间的数字,发现60<89,再次舍去左半边,继续右半边的查询。
完整过程见下图:

同理,根据上图,我们每次查找中间的数字,舍去一半的区间,就可以仅仅循环3次就查找到了待查找的数字。
如果我们要从1~20的数组中查找7,过程也是如下:

我们可以写代码了。一共需要三个指针,left,right和mid,分别代表当前的区间的左右端点。

#include<bits/stdc++.h>
using namespace std;
int a[100000];
int main(){
  int n;
  cin>>n;
  for(int i=1;i<=n;i++)cin>>a[i];
  int d;
  cin>>d;
  int left=1,right=n;
  while(left<=right){
    int mid=(left+right)/2;
    if(a[mid]>d)right=mid-1;//数字在左区间
    else if(a[mid]<d)left=mid+1;//数字在右区间
    else{
      cout<<mid<<endl;return 0;//找到数字
    }
  }
  cout<<-1;//未找到
  return 0;
}

相关文章

微信公众号

最新文章

更多