二分算法(查找)
问题:在数组中查找某一个数字x=4的下标
(图片来源网络,侵删)
例:arr:1 3 4 6 10 20 21 22
显然,数字4的下标为3。
1、线性查找,一个个地去遍历,时间复杂度为O(n)
2、二分查找,时间复杂度为O(logn) 前提:arr一定要单调
下面具体介绍二分查找:
现在,L=1,R=8(要查找的数组范围,数组下标从1开始)
(图片来源网络,侵删)
mid=(L+R)/ 2 =4,arr[mid]=6 大于4,更新R=mid-1(因为是单调的)
L=1,R=3
mid=(L+R)/ 2 =2,arr[mid]=3 小于4,更新L=mid+1
L=3,R=3
mid=(L+R)/ 2 =3,arr[mid]=4 等于4,找到了
#include #include using namespace std; const int N=100; int arr[N]; int binarySearch(int arr[],int n,int x){ sort(arr+1,arr+n+1);//先排序 int L=1,R=n; int ans=-1; while(L>1;//右移一位即除以2 if(arr[mid]==x){ ans=mid; break; } if(arr[mid]>x){ R=mid-1; }else{ L=mid+1; } } return ans; } int main(){ int n; cin>>n; for(int i=1;i>arr[i]; } int x; cin>>x;//要查找的数字 cout
文章版权声明:除非注明,否则均为主机测评原创文章,转载或复制请以超链接形式并注明出处。
还没有评论,来说两句吧...