日志13

二分查找
二分查找是一种在有序数组中查找特定元素的搜索算法。搜索过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜索过程结束；如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空，则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半。
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=1e3+5;
int n,m;
int a[N];
void binarySearch(int m)
{
int left=0,right=n-1;
int mid;
while(left<=right)
{
mid=left+(right-left)/2;
if(a[mid]==m)
{
cout<<"YES"<<endl;
return;
}
else if(a[mid]>m)
{
right=mid-1;
}
else
{
left=mid+1;
}
}
cout<<"NO"<<endl;
}
int main()
{
cin>>n;
for(int i=0;i<n;i++)
{
cin>>a[i];
}
sort(a,a+n);
cin>>m;
binarySearch(m);
return 0;
}

这段代码首先定义了一个名为`binary_search`的函数，该函数接受一个整数数组、数组的左边界、右边界和要查找的元素作为参数。然后，它计算中间索引并检查该索引处的元素是否等于要查找的元素。如果是，则返回中间索引。如果要查找的元素小于中间元素，则在左半部分数组中递归查找。如果要查找的元素大于中间元素，则在右半部分数组中递归查找。如果数组为空（即左边界大于右边界），则返回-1，表示元素不在数组中。