二分查找，什么时候用right=mid-1，什么时候用right=mid？

Question

我在 leetcode 上解决这个问题 https://leetcode.com/problems/leftmost-column-with-at-least-a-one/ 但我想不出一个直观的答案。

为什么右（或高）指针有时设置为 mid - 1，为什么有时设置为 mid 是正确的？

我知道我们必须始终设置 left = mid + 1 因为整数除法。当只剩下两个元素时，我们需要设置mid + 1以避免死循环。

但是在什么情况下使用 right = mid - 1，vs right = mid？

谢谢。

Answer 1

假设您正在对如下序列进行二进制搜索

.....0, 0, 0, 0, 1, 1, 1, 1, ....

你的决策函数 fn returns true 如果 1 的值保持 true。

现在考虑您的目标是找到 0 的最后位置。在二分查找的每一步中，我们都会减少搜索space，这样我们就可以确定位置在范围内。如果 fn returns true for mid 你知道 0 的最后位置将小于 mid （因为你想要最后一次出现 0 必须在第一次出现 1 之前）。因此，您将更新 right=mid-1。如果fn return false left=mid.

现在考虑您的目标是找到 1 的第一次出现。现在如果 fn returns true 你将更新 right=mid 因为你知道 1 的第一次出现将在这个位置或它的左边。在这种情况下，如果 fn returns false，您将需要更新 left=mid+1.

Answer 2

小型数组的线性搜索优于二分搜索。因此，使用或不使用 -1 并不重要，因为您的搜索应该在 right-left < N 时中断，然后您可以在两者之间进行线性搜索（N 是一个参数，您可以通过运行基准找到适合您的特定应用程序。

我上次测量时，整数的 Iirc N 约为 700。

Answer 3

实现二分查找的模板有3个
模板 1：不依赖于其他元素和相邻元素。

while(left <= right){
    int mid = (int)Math.floor((left + right)/2);
    if(nums[mid] == target) return mid;
    else if(nums[mid] < target) {
        left = mid + 1;
    } else {
        right = mid - 1;
    }
}

模板 2：当搜索值需要访问当前索引及其右邻的索引时使用

while(left < right){
   // Prevent (left + right) overflow
   int mid = left + (right - left) / 2;
   if(nums[mid] == target){ return mid; }
   else if(nums[mid] < target) {
      left = mid + 1; }
   else {
      right = mid; }
}

模板 3：当搜索值需要访问当前索引及其左右相邻索引时使用

 while (left + 1 < right){
    // Prevent (left + right) overflow
    int mid = left + (right - left) / 2;
    if (nums[mid] == target) {
        return mid;
    } else if (nums[mid] < target) {
        left = mid;
    } else {
        right = mid;
    }
}

来源：LeetCode Explore

二分查找，什么时候用right=mid-1，什么时候用right=mid？

Binary search, when to use right = mid - 1, and when to use right = mid?

sorting

algorithm

pointers

binary-search