二分搜索条件

Question

在使用二进制搜索解决搜索问题时，循环条件有时是while low < hi，有时是while low <= hi。

我试图根据我得到的输出在这两个条件之间进行切换，但我希望对如何区分这两个条件有一个更好的直觉，并知道何时使用哪个条件。

选择要使用的条件的简单方法是什么？

Answer 1

如果实现得当，这两种方法理想情况下都能正确地解决问题。就我个人而言，我喜欢遵循low <= hi方法。

伪代码：

while(low <= hi){
    int mid = (low + hi)/2;
    if(check condition for mid){
       result = mid;
       hi = mid - 1; or low = mid + 1;
    }else{
       low = mid + 1; or hi = mid - 1;
    }
}

在上面的代码中，我们检查mid是否满足我们的解决方案的可能答案的条件，并根据这一条件向左或右子序列移动。还要注意，向左或向右子序列的移动取决于我们是否想要找到问题的最大值或最小值。