c++ - 理解二元搜索问题中的范围问题

问题描述

编辑：
添加有关代码背后逻辑的更多详细信息。感谢@Stef。

我正在尝试在 LeetCode ( https://leetcode.com/problems/find-the-duplicate-number/ ) 中解决算法问题。

下面是我解决这个问题的方法，它使用了二分搜索思想。
代码的基本逻辑是，我试图使用二进制搜索在 [1, n] 范围内找到重复的数字。

例如，如果我要在列表 [1, 3, 4, 2, 2] 中找到重复的 num。
首先，计算[1, 4]的中点，因为起点是1，终点是4，所以中点是2。然后我用cntRange函数计算列表中有多少个数字在[ 1, 2]。如果数字的数量（我们有 1、2、2、3 个数字）超过了应有的数量（应该是 2），我们通过将端点设置为中点来缩小范围并继续二进制搜索，直到完成搜索我们返回起点的现值，也就是复制的起点。

class Solution {
public:
    int findRepeatNumber(vector<int> &nums) {
        // special case we return -1
        if (nums.size() < 2) {
            return -1;
        }

        // binary search to cnt the numbers in certain range
        int start = 1;
        int end = nums.size() - 1;
        while (end >= start) {

            int mid = ((end - start) >> 1) + start;
            int cnt = cntRange(nums, start, mid);

            if (end == start) {
                if (cnt > 1) {
                    return start;
                } else {
                    break;
                }
            }

            if (cnt > (mid - start + 1))
                end = mid;
            else
                start = mid + 1;
        }
        return -1;
    }

    int cntRange(vector<int> &nums, int start, int end) {
        int cnt = 0;
        for (int i = 0; i < nums.size(); ++i) {
            if (nums[i] >= start && nums[i] <= end)
                cnt++;
        }
        return cnt;
    }
};

这个方法传入了 LeetCode，但是我很好奇 [1, n] 的范围，如果范围是 [0, n-1] 呢？

我尝试了两个测试集：一个是 [0, 1, 2, 0, 4, 5, 6]
另一个是 [2, 3, 1, 0, 2, 5, 3]
他们都失败了，所以我回去到我的代码尝试解决这个问题。

我将 start int 初始化为 0，并将 cnt 比较条件
从 cnt > (mid - start + 1) 更改为 cnt > (mid - start)。
但是在这种情况下，只有第一个测试通过了，我仍然无法通过第二个测试。

我仍然认为这个问题出现在cnt比较过程中，但不知道如何解决这个问题。
有人可以帮我吗？

标签： c++algorithmbinary-search

c++ - 理解二元搜索问题中的范围问题

问题描述

解决方案

推荐阅读