java - 二分查找权应该是 nums.length 还是 nums.length - 1？

Question

我总是对二进制搜索右边界感到困惑。例如，如果我们想在有序数组中找到目标的最后一个索引，代码应该是：

public int binarySearchLarger(int[] nums, int target) {
        int l = 0;
        int r = nums.length - 1;
        while (l < r) {
            int m = l + (r - l + 1) / 2;
            if (nums[m] < target) l = m;
            else if(nums[m] > target) r = m - 1;
            else l = m;
        }
        if (nums[l] == target) return l;
        else return -1;
    }

但是我看到很多帖子说如果我们想要while(l<r)，那么r应该是nums.length，在这种情况下，代码变成：

public int binarySearchLarger(int[] nums, int target) {
        int l = 0;
        int r = nums.length;
        while (l < r) {
            int m = l + (r - l + 1) / 2;
            if (nums[m] < target) l = m;
            else if(nums[m] > target) r = m - 1;
            else l = m;
        }
        if (nums[l] == target) return l;
        else return -1;
    }

但是在这种情况下，if (nums[m] < target) l = m;会抛出arrayindexoutofbound异常。我的问题是：我们应该什么时候使用r = nums.length - 1，什么时候应该使用r = nums.length?

标签： javaalgorithmbinary-search

Answer 1

我这样做：

int findEndIndex( vector<int> &nums, int target ){
    int l = 0, r = nums.size() - 1;
    while( l < r ){
        int m = (l + (r - l) / 2) + 1;
        if( nums[m] == target )
            l = m;
        else if( nums[m] < target )
            l = m + 1;
        else
            r = m - 1;
    }
    return l >= nums.size() || nums[l] != target ? -1 : l;
}