首页 > 代码库 > 入门之二分搜索
入门之二分搜索
1 /* 2 入门之二分查找 3 时间复杂度:O(logn) 4 只能查找已排序好的数组 5 通过不断比较中间值,确定keyword在中间值的左边或右边,直到找到或结束 6 */ 7 #include<iostream> 8 using namespace std; 9 int a[] = {1,2,3,4,5,6,7,8,9}; 10 bool binary_search(int,int,int); 11 int main() 12 { 13 int key; 14 while(1){ 15 cout << "keyword:"; 16 cin >> key; 17 if(binary_search(key,0,8)) 18 cout << "Find success" << endl; 19 else 20 cout << "Find failed" << endl;} 21 } 22 bool binary_search(int k,int l,int r)//循环实现 23 { 24 while(l <= r) 25 { 26 int m = (l + r)/2; 27 if(a[m] == k) return true; 28 else if(a[m] > k) r = m-1; 29 else l = m+1; 30 } 31 return false; 32 } 33 bool binary_search(int k,int l,int r)//递归实现 34 { 35 if(l > r) return false; 36 int m = (l + r)/2; 37 if(a[m] == k) return true; 38 else if(a[m] > k) return binary_search(k,l,m-1); 39 else binary_search(k,m+1,r); 40 }
入门之二分搜索
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。