二分查找的最高索引

Question

所以我正在学习如何进行二进制搜索，我理解这个概念，但我不明白为什么我们需要

(right - left)

获得最高指数。我无法在脑海中想象这个：/

class Solution {
    public int search(int[] nums, int target) {
    int pivot;
    int left = 0;
    int right = nums.length - 1;
    while (left <= right) {
         pivot = left + (right - left) / 2;
         if (nums[pivot] == target) return pivot;
         if (target < nums[pivot]) right = pivot - 1;
         else left = pivot + 1;
    }
    return -1;
    }
 }

Answer 1

left + (right - left) / 2

与

相同

(right + left) / 2

他们都取左右的平均值。使用前者的目的是防止整数溢出。如果right + left大于变量可以进位，即使这个变量可以进位它们的平均值，结果也是错误的，因为right + left会导致溢出。

另一方面，先计算 (right - left) / 2 并添加 left 以防止溢出。