对二元seach问题中值域问题的认识

Question

编辑:
添加有关代码背后逻辑的更多细节。Thx到@stef。

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;
    }
};

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

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

Answer 1

你提到的两种情况的问题是：

start = mid + 1;

mid的值永远不能变为负值，因此在第一次到达这条线之后，start的最小值永远不能小于1。这意味着在进行二进制搜索时，您永远不会看到索引0处的值。