首页 > 代码库 > 二分查找、二分查找大于等于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的最后一个元素