本文是关于二进制搜索及其在C++中的实现。

什么是二进制搜索？

"二进制"这个词实际上是指'二'。
因此，预计会有与"二"相关的东西。
在线性搜索的情况下，我们从阵列的开头开始并继续逐渐检查。

现在，可能存在搜索元素属于阵列的结束部分，我们保证了我们的时间检查线性搜索的所有其他元素Incase。
对于任何搜索算法，最重要的是其时间复杂性。

虽然具有复杂性的线性搜索似乎做得很好，但它实际上不是。
想想任何大数据集，它会花多少时间，但它是O(n)。
我们买不起。
这里有二进制搜索，时间复杂得多。

二进制搜索是基于排序的想法。
为了操作二进制搜索，需要对输入数组进行排序。
所以，想法是，我们可以从中间元素开始。
如果搜索元素小于中间元素，则无需检查中间元素的右半部分上的元素，即，我们可以跳过大于中间元素的元素。
由于数组被排序，因此它保证了右侧的没有元素可以是搜索元素。

另一方面，如果搜索元素大于中间元素，则无需检查中间元素的左半部分的元素，即，我们可以跳过小于中间元素的元素。
由于该数组被排序，因此保证了左侧的未在左侧的元素可以是搜索元素。

二进制搜索算法

考虑到0-索引，1.初始化左= 0 2.初始化变量右=数组大小 - 1 3.在left <=右侧进行计算中段=(左+右)/2如果阵列[mid] ==搜索元素返回REAL ELSELY IF ARRAY [MID] <SEARCEENTEM SET LEFT = MID +1 ELSE/ARRAY [MID]>搜索元素SET RIGIT = MID -1结束时4.返回FALSE

时间复杂性

用于二进制搜索的O(logn)递归关系是; t(n)= t(n/2)+ o(1)(因为我们始终只搜索一半)解决递归关系，我们发现时间复杂度为O(logn)

解释示例

让输入阵列为：1,2,3,4,5,6让搜索元素为：2所以，左= 0右= 5(阵列大小= 6)迭代1左<右中期=(0 + 5)/2 = 2 array [mid]> 2所以，左= 0右= mid-1 = 1迭代2左<右中段=(0 + 1)/2 = 0阵列[mid] <2所以，左= mid + 1 = 1右= 1迭代3左=右中期=(1 + 1)/2 = 1阵列[mid] == 2返回真正的搜索元素

二进制搜索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;
}

递归解决方案

#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