首页 > 代码库 > 二分查找
二分查找
二分查找算法，又称折半查找，是一种在有序数组中查找某一特定元素的搜索算法。
搜素过程从数组的中间元素开始，
1）如果中间元素正好是要查找的元素，则搜素过程结束；
2）如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找；
3）数组为空，退出
代码如下：
1 int binary_search(int A[], int n, int target) 2 { 3 int low = 0, high = n - 1, mid = -1; 4 while (low <= high) 5 { 6 mid = (low + high) / 2; 7 if (A[mid] == target) 8 { 9 break;10 }11 else if (A[mid] < target)12 {13 low = mid + 1;14 }15 else16 {17 high = mid - 1;18 }19 }20 21 return (low <= high) ? mid : -1;22 }
折半查找时间
T(n) = T(n/2) + c ==>> T(n) = O(lbn)
二分查找
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。