二分查找原理和实现
前言
区间
lower_bound 和 upper_bound 和 binary_search 和 equal_range
实现
分类:
IT文章
•
2022-05-01 10:41:42
注意计算的区间是左闭右开区间[)还是左闭右闭区间[]，两者的代码是不太一样的。
{
int left = 0;
int right = n - 1; //比如说只有一个情况下
while (left <= right ) { //需要等于号，不然会进不来
int middle = left + (right - left) >> 1;
if (target < array[middle]) {
right = middle - 1;
}
else if (target > array[middle]) {
left = middle + 1;
}
else {
return middle;
}
}
return -1;
}
// 左闭右开区间
int search4(int array[], int n, int target) {
int left = 0;
int right = n;
while (left < right) {
int middle = left + (right - left) >> 1;
if (target < array[middle]) {
right = middle;
}
else if (target > array[middle]) {
left = middle + 1;
}
else {
return middle;
}
}
return -1;
}
左闭右闭区间，right = n - 1，left <= right，right = middle - 1
左闭右开区间，right = n，left < right，right = middle
为什么会这样呢？比如说n为1的时候，right此时为0，此时left也为0，需要等号才能进行while 循环。
还有需要注意的是，计算middle的时候，先计算减法是为了避免溢出。
STL的使用：
lower_bound：找到第一个 >= target的位置
比如说给定的数组[1,2,2,2,3]
使用lower_bound返回的是第一个值为2的迭代器；
使用lower_bound
- 如果mid < val，显然mid本身及其左边的元素都不可能是答案了，则把first置为 mid + 1。
- 如果mid >= val，答案可能是mid本身或者mid左边的元素，则把last置为mid。
使用upper_bound
- 如果mid <= val，显然mid其左边的元素都不可能是答案了，则把first置为 mid + 1。
- 如果mid > val，答案可能是mid右边的元素，所以把last设置成mid。
binary_search：查找某个元素是否出现
equal_range：查找某个元素出现的起止位置（终止位置为最后一次出现的位置加1）
// 二分查找找数组下标
int search(int array[], int low, int high, int target) {
if (low > high) {
return -1;
}
int mid = (low + high) / 2;
if (array[mid] < target) {
return search(array, low, mid, target);
}
else if (array[mid] > target) {
return search(array, mid + 1, high, target);
}
else {
return mid;
}
}
// 迭代版本
int search2(int array[], int low, int high, int target) {
while (low <= high) {
int mid = (low + high) / 2;
if (array[mid] > target) {
high = mid-1;
}
else if (array[mid] < target) {
low = mid+1;
}
else {
return mid;
}
}
return -1;
}
