二分查找减少搜索space

Question

class Solution {
public:
    int search(vector<int>& nums, int target) {
        if(nums.empty()) return -1;

        int lo=0, hi=nums.size()-1;
        while(lo<hi) {
            int mid=lo+(hi-lo)/2;
            //if element found at position mid, return mid
            if(nums[mid]==target) return mid;
            if(nums[mid]<target) lo=mid+1;
            //why not hi=mid-1, since if mid _could_ have our answer, we would 
            //have already returned above
            else hi=mid;
        }
        
        // if element not found, return -1;
        return nums[lo]==target ? lo : -1;
    }
};

我正在寻找设置 hi=mid 的直观解释（特别是 while 循环条件为 lo<hi 而不是 lo<=hi）。我认为我们应该将其设置为 hi=mid-1，因为我们知道 mid 不能包含我们的答案（如果包含，那么我们早就返回了）。是的，我可以在几个例子中尝试一下，但我试图直观地理解搜索 space 在 开发逻辑 时如何减少（在开始编码之前），以便我可以想出一个适用于所有示例的具体算法。

Answer 1

I am seeking an intuitive explanation for setting hi=mid (specifically with the while loop condition as lo<hi and not lo<=hi). I think we should set it as hi=mid-1, since we know that mid cannot contain our answer (if it did, then we would have already returned).

这里有两个主要的潜在问题：

正确。函数是否终止并为所有输入返回正确答案？
- 和hi=mid，是的。为此，我们可以观察到当循环条件lo<hi成立时，mid总是严格小于hi但不小于lo，因此设置mid=hi减少搜索间隔。我们还可以观察到，当执行该替代方案时，如果目标值存在，则目标值必须在缩小的区间内。由于搜索 space 是有限的并且在每次迭代时都会减少，因此如果不能更快地找到目标，计算最终必须达到间隔大小 1（因此终止）。
- 和hi=mid-1，也是。论点是一样的，但值得注意的是 mid == lo 的情况可能会导致 hi 被设置为小于 lo 的可能性。这在编写函数时不会出现实际问题，但它有点不整洁。
效率。该函数能否以更少的步骤得出正确的结果？

使用 hi=mid-1 不会使函数渐近更快。无论哪种方式都是 O(log n) 。此外，在任何给定的问题上，这两个备选方案将测试不同的值序列，因此当目标值存在时，任一备选方案可能恰好比另一个方案在更少的周期内完成。直觉表明，将搜索间隔缩小一点点平均来说会略有优势，尤其是在目标值不存在的情况下，但这种增益在比例上微不足道，除非在间隔已经非常小的周期中。

I am trying to intuitively understand how the search space reduces while developing the logic (before getting to coding) so that I can come up with a concrete algo that can work on all examples.

这两种选择都有效，没有理由期望明显的速度差异。那么，它归结为风格和个人情感。在这种情况下，我个人更喜欢 hi=mid，以避免出现 hi < lo 的情况。其他人可能更喜欢 hi=mid-1 对称。

旁注：另一方面，不能将 lo=mid+1 更改为 lo=mid。因为 mid=lo+(hi-lo)/2 有可能导致 mid==lo，所以需要 lo=mid+1 替代方法来确保间隔在每个循环中都缩小。

二分查找减少搜索space

Reduction of search space in binary search

c++

algorithm

binary-search