个人笔记
题意：数组中找某个数，问是否存在，存在返回YES，否则返回NO
这题你可以用最简单的一遍for过，我就想做个二分搜索的笔记
思路：先排个序，然后比较中间的，目标数比它大，则在右边，反之左边
bool binary_search(int x){
//x的存在范围是k[l],k[l+1]...k[r-1]
int l=0,r=n;
//直到范围为空
while(l-r>=1){
int m=(l+r)/2;
if(k[m]==x)return true;
else if(k[m]<x)l=m+1;
else r=m;
}
return false;
}
但其实C++的STL中存在这个功能的函数binary_search(); 运用也很简单，头文件是<algorithm>
if(binary_search(k,k+n,x))cout<<"YES"<<endl;
else cout<<"NO"<<endl;
但我们要明白它的原理，不然让你面试手写原理的时候，不就懵了吗
网友评论