二分查找的几种情况-C++实现

发表于 | 分类于

文章阅读

二分查找详解

思路

前提： 已排序数组

思路：

  1. 从已经排好序的数组或区间中取出中间位置的元素，判断该元素是否满足要搜索的条件，如果满足，停止搜索，程序结束。
  2. 如果正中间的元素不满足条件，则从它两边的区域进行搜索。由于数组是排好序的，可以利用排除法，确定接下来应该从这两个区间中的哪一个去搜索。
  3. 通过判断，如果发现真正要找的元素在左半区间的话，就继续在左半区间里进行二分搜索。反之，就在右半区间里进行二分搜索。

难点： 判断逻辑，什么时候返回

基本的二分查找

题目： 从一个排好序的数组里 {1, 3, 4, 6, 7, 8, 10, 13, 14}查看一下数字 8 是否在里面，如果在，返回它的下标，否则返回 -1。

递归实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <vector>

using namespace std;

int binarySearch_recursion(const vector<int> &nums, int target, int low, int high){
    if (low > high) return -1;

    int middle = low + (high - low) / 2;
    if (nums[middle] == target)
        return middle;

    if (target < nums[middle])
        return binarySearch_recursion(nums, target, low, middle - 1);
    else
        return binarySearch_recursion(nums, target, middle + 1, high);
}

迭代实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int binarySearch_iteration(const vector<int> &nums, int target, int low, int high) {
    while (low <= high){
        int middle = low + (high - low) / 2;
        if (nums[middle] == target)
            return middle;

        if (target < nums[middle])
            high = middle - 1;
        else
            low = middle + 1;
    }

    return -1;
}

查找确定的边界

题目： 输入的数组是：{1, 3, 4, 6, 8, 8, 8, 13, 14}，目标数是 8，那么返回 {4, 6}，其中 4 是 8 第一次出现的下标位置，6 是 8 最后一次出现的下标位置。

迭代实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
// 下边界
int searchLowerBound(const vector<int> &nums, int target, int low, int high){
    while (low <= high){
        int middle = low + (high - low) / 2;
        if (nums[middle] == target && (middle == 0 || nums[middle-1] < target))
            return middle;

        if (target <= nums[middle])
            high = middle - 1;
        else
            low = middle + 1;
    }

    return -1;
}

// 上边界
int searchUpperBound(const vector<int> &nums, int target, int low, int high){
    while (low <= high){
        int middle = low + (high - low) / 2;
        if (nums[middle] == target && (middle == nums.size() - 1 || nums[middle+1] > target))
            return middle;

        if (target < nums[middle])
            high = middle - 1;
        else
            low = middle + 1;
    }
}

查找模糊的边界

题目： 从数组 {1, 3, 4, 6, 7, 8, 10, 13, 14}中找到第一个大于 8 的数。

迭代实现：

1
2
3
4
5
6
7
8
9
10
11
12
int firstGreaterThan(const vector<int> &nums, int target, int low, int high){
    while (low <= high){
        int middle = low + (high - low) / 2;
        if (nums[middle] > target && (middle == 0 || nums[middle-1] <= target))
            return middle;

        if (target < nums[middle])
            high = middle - 1;
        else
            low = middle + 1;
    }
}

测试

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int main() {
    vector<int> nums = {1, 3, 4, 6, 7, 8, 10, 13, 14};
    vector<int> nums_1 = {1, 3, 4, 6, 8, 8, 8, 13, 14};
    int target = 8;
    int low = 0;
    int high = nums.size();

    // 查找指定值，递归写法
    cout << binarySearch_recursion(nums, target, low, high) << endl;  // 5
    cout << binarySearch_iteration(nums, target, low, high) << endl;  // 5

    // 查找上下边界
    cout << searchLowerBound(nums_1, target, low, high) << endl;  // 4
    cout << searchUpperBound(nums_1, target, low, high) << endl;  // 6

    // 查找模糊边界
    cout << firstGreaterThan(nums, target, low, high) << endl; // 6

    return 0;
}