Leetcode 34. 使用 ArrayIndexOutOfBoundsException 查找排序数组中元素的第一个和最后一个位置

Question

class Solution {
public int[] searchRange(int[] nums, int target) 
{
    int first = firstIndex(nums, 0, nums.length, target);
    int last = lastIndex(nums, 0, nums.length, target);

    return new int[] {first, last};
}

public int firstIndex (int[] nums, int left, int right, int target)
{
    while (left <= right)
    {
        int pivot = left + (right - left) / 2;
        if (nums[pivot] == target)
        {

            if (pivot == left || nums[pivot - 1] < nums[pivot]) 
                // it means the search on left side is done or mid is the first occurance in the array
                return pivot;

            else 
                // still go left
                right = pivot - 1;
        }
        else if (nums[pivot] > target)
            right = pivot - 1;
        else
             left = pivot + 1;
    }
    return -1;
}

public int lastIndex (int[] nums, int left, int right, int target)
{
    while (left <= right)
    {
        int pivot = left + (right - left) / 2;
        if (nums[pivot] == target)
        {

            if (pivot == right || nums[pivot] < nums[pivot + 1])
                // it means the search on the right side is done or mid is the last occurance in the array
                return pivot;
            else 
                // still go right
                left = pivot + 1;
        }
        else if (nums[pivot] > target)
            right = pivot - 1;
        else 
            left = pivot + 1;
    }
    return -1;
}

}

这是我使用二进制搜索的解决方案。当我运行代码可以接受但是不能提交。在 if (nums[pivot] == target) 处存在 ArrayIndexOutOfBoundsException。我不明白为什么会这样。我研究了解决方案。大多数解决方案都使用这种方式。我不知道如何摆脱这个错误。有人可以帮我解释一下吗？？？？太感谢了！！！！

Answer 1

我很确定问题出在你的电话上`

int first = firstIndex(nums, 0, nums.length, target);
int last = lastIndex(nums, 0, nums.length, target);`

由于第三个参数指的是数组最右边的索引，nums.length 1 太高了，因为数组是从 0 开始的。在寻找比最右边的元素更大的东西时，我用你的代码复制了 jdoodle 上的错误，并将第一行中的 nums.length 更改为 nums.length-1 将错误推入了第二次调用。在第二次调用中将 nums.length 替换为 nums.length-1 使其完全消失。

单击 https://www.geeksforgeeks.org/binary-search/ 处的 java 选项卡，您可以看到他们使用 n -1。

Leetcode 34. 使用 ArrayIndexOutOfBoundsException 查找排序数组中元素的第一个和最后一个位置

Leetcode 34. Find First and Last Position of Element in Sorted Array with ArrayIndexOutOfBoundsException

java

java.lang.class

indexoutofboundsexception

java.lang