首页 > 代码库 > 二分查找、二分查找大于等于key的第一个元素、二分查找小于等于key的最后一个元素
二分查找、二分查找大于等于key的第一个元素、二分查找小于等于key的最后一个元素
二分查找很简单,二分查找的变形需要注意一些细节。
1、当找大于等于key的第一个元素,或者查找小于等于key的最后一个元素时,
循环条件是 low < high,这和基本的二分查找不同,
但需要在循环退出的时候,判断是否满足条件;
2、如果是找最后一个满足条件的情况,
下限移动时不能用 low=mid+1;而应该用 low=mid;
此时,mid计算时应该用 mid=(low+high+1)/2,
保证 最后low、high相差1时不会陷入死循环,
循环退出后,下限可能是结果;
3、如果是找第一个满足条件的情况,
移动时不能用 high=mid-1;而应该用 high=mid;
此时,mid计算时还是用 mid=(low+high)/2,想想为什么?
循环退出后,上限可能是结果;
#include <iostream> using namespace std; #define N 8 int binary_search(int a[], int low, int high, int key) { while (low <= high) { int mid = (low + high)/2; if (a[mid] == key) { return mid; } else if (a[mid] > key) { high = mid - 1; } else { //a[mid] < key low = mid + 1; } } return -1; } int binary_down_bound(int a[], int low, int high, int key) { while (low < high) { int mid = (low + high + 1)/2; if (a[mid] > key) { high = mid -1; } else { //a[mid] <= key low = mid; } } if (a[low] <= key) { return low; } else { return -1; } } int binary_up_bound(int a[], int low, int high, int key) { while (low < high) { int mid = (low + high)/2; if (a[mid] < key) { low = mid +1; } else { //a[mid] >= key high = mid; } } if (a[high] >= key) { return high; } else { return -1; } } int main () { int a[] = { 1,2,3,4,6,6,7,8 }; int pos = -1; int key = 0; cout << "intput key:"; cin >> key; //pos = binary_search(a, 0, N-1, key); //pos = binary_down_bound(a, 0, N-1, key); pos = binary_up_bound(a, 0, N-1, key); cout << "binary search result:" << pos << endl; }
本文出自 “天眼神童的新家” 博客,请务必保留此出处http://tianyanshentong.blog.51cto.com/3356396/1560237
二分查找、二分查找大于等于key的第一个元素、二分查找小于等于key的最后一个元素
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。