关于BinarySearch算法中边界调整为mid±1的疑问

Great question—this is one of the most common sticking points when learning binary search, so let’s break it down clearly.

First, let’s remember what happens in each iteration: we check the element at mid against our target. Since we’ve already verified that numbers[mid] is not the target (we would have returned early if it was), there’s no reason to keep mid in our future search range. That’s the core idea here—we’re actively shrinking the search space by eliminating the one element we know can’t be the target.

Let’s look at the two cases: #

1. When numbers[mid] < target:
   The target has to be in the right half of the current range. Since numbers[mid] is too small, we don’t need to include it anymore. If we set min = mid instead of mid+1, we risk getting stuck in an infinite loop. For example:

   • Take the array [1, 3] and target 2.
   • First iteration: min=0, max=1, mid=0. numbers[0] = 1 < 2.
   • If we set min=mid (0), the next iteration will have the exact same min and max values—mid will still be 0, and we’ll keep checking the same element forever.
   • Using min=mid+1 moves us to the right half, and the loop will eventually exit correctly when min > max.

2. When numbers[mid] > target:
   Similar logic applies here—the target is in the left half, and numbers[mid] is too large to be the target. Setting max=mid-1 removes this element from the search range. If we used max=mid instead, we could hit an infinite loop too:

   • Take the array [1, 3] and target 0.
   • First iteration: min=0, max=1, mid=0. numbers[0] = 1 > 0.
   • If we set max=mid (0), the next iteration will still have min=0, max=0, mid=0—we’ll keep checking numbers[0] forever instead of exiting and returning -1.

To sum it up: #

Using mid+1 and mid-1 ensures that every iteration of the loop reduces the search space by at least one element, which guarantees the loop will eventually terminate. If we stuck with mid, we’d have cases where the search space never shrinks, leading to infinite loops and incorrect results. It’s all about maintaining a tight, valid search range that excludes elements we’ve already ruled out.

内容的提问来源于stack exchange，提问作者DevOnix