C++中的二分查找

Posted on by

本文是关于二分查找及其在 C++ 中的实现。

目录

“二进制”这个词实际上是指“二”。所以，可以预见的是，会有一些与“二”相关的东西。在线性搜索的情况下，我们从数组的开头开始并逐渐检查。

现在，可能存在搜索元素属于数组末尾部分的情况，我们一直在浪费时间检查所有其他元素以防线性搜索。对于任何搜索算法来说，最重要的是它的时间复杂度。尽管复杂度为 O(n) 的线性搜索似乎做得很好，但实际上并非如此。想想任何大型数据集，它需要多少时间，尽管它是 O(n)。我们负担不起这样的。这是时间复杂度要低得多的二分搜索。

二分查找是基于排序的思想。为了操作二分查找，输入数组需要排序。所以，这个想法是，我们可以从中间元素开始。如果搜索元素小于中间元素，则不需要检查中间元素右半边的元素，即，我们可以跳过大于中间元素的元素。由于数组已排序，因此可以保证右侧没有元素可以作为搜索元素。

另一方面，如果搜索元素大于中间元素，则不需要检查中间元素左半边的元素，即可以跳过小于中间元素的元素。由于数组已排序，因此可以保证左侧的任何元素都不能成为搜索元素。

二分搜索算法

考虑到 0 索引，

  1. Initialize a variable left=0
  2. Initialize a variable right=array size – 1
  3. While left <= right
            Do
            Calculate mid= (left + right)/2
            If array[mid]==searching element
                Return True
            Else If array[mid] < searching element
                Set left=mid +1
            Else //array[mid] > searching element
                Set right=mid –1
            END While
  4. Return False

时间复杂度

O(logn)
对于二分查找，递归关系是；
T(n)=T(n/2)+ O(1)
（因为我们总是只搜索一半）
求解递归关系，我们发现时间复杂度为 O(logn)

示例说明

设输入数组为：
1, 2, 3, 4, 5, 6
设搜索元素为：2
所以，
Left=0
Right=5（数组大小=6）
迭代1
        Left<right
        Mid=(0+5) /2 = 2
        Array[mid]>2
        So, left=0
        Right=mid-1=1
迭代 2
        Left<right
        Mid=(0+1)/2 = 0
        Array[mid]<2
        So, left=mid+ 1=1
        Right=1
迭代 3

Left=right
        Mid=(1+1)/2 = 1
        Array[mid]==2
        Return True

找到的搜索元素

二分查找C++实现<

迭代解决方案

#include <bits/stdc++.h>
using namespace std;
 
int binarySearch(vector<int> a,int n, int x){
 
    int left=0; //initialize left
    int right=n-1; //initialize right
    int mid;
    while(left<=right){
        mid=(left+right)/2; //calculate mid
        if(a[mid]==x) //if the a[mid] is x value is found
        return 1;
        else if(a[mid]<x){ //if a[mid] is less than x, we need to search only the right half
            left=mid+1;
        }
        else //if a[mid] is less than x, we need to search only the left half
        right=mid-1;
    }
    //if not returned from the loop, it ensures value is not present
    return -1;
}
 
int main(){
    int n,item,x;
  cout<<"Enter number of elements in the array\n";
  cin>>n;
  vector<int> a;
  //input the array
  cout<<"Enter the elements of your array\n";
  for(int j=0;j<n;j++){
    scanf("%d",&item);
    a.push_back(item);
  }
  cout<<"Enter the value you want to search\n";
  cin>>x;
  int result=binarySearch(a,n,x); //function to output search result
  if(result!=-1)
  cout<<x<<" is present in the array"<<endl;
  else
  cout<<x<<" is not present in the array"<<endl;
 
  return 0;
}

输出：

Enter number of elements in the array
6
Enter the elements of your array
4 6 8 9 10 11
Enter the value you want to search
11
11 is present in the array

递归解决方案

#include <bits/stdc++.h>
using namespace std;
 
int binarySearch(vector<int> a,int left,int right, int x){
 
    if(left>right)
    return -1;
 
    int mid=(left+right)/2;
 
    if(a[mid]==x)
        return 1;
    else if(a[mid]<x)
        return binarySearch(a,mid+1,right,x);//search in the right half
    else
    return binarySearch(a,left,mid-1,x);//search in the left half
}
 
int main(){
  int n,item,x;
  cout<<"Enter number of elements in the array\n";
  cin>>n;
  vector<int> a;
  //input the array
  cout<<"Enter the elements of your array\n";
  for(int j=0;j<n;j++){
    scanf("%d",&item);
    a.push_back(item);
  }
  cout<<"Enter the value you want to search\n";
  cin>>x;
  int result=binarySearch(a,0,n-1,x); //function to output search result
  if(result!=-1)
  cout<<x<<" is present in the array"<<endl;
  else
  cout<<x<<" is not present in the array"<<endl;
 
  return 0;
}

输出：

Enter number of elements in the array
3
Enter the elements of your array
4 7 9
Enter the value you want to search
6
6 is not present in the array

这就是 C++ 中的二分搜索

推荐阅读：