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。我不明白为什么会这样。我研究了解决方案。大多数解决方案都使用这种方式。我不知道如何摆脱这个错误。有人可以帮我解释一下吗????非常感谢!!!
我很确定问题出在您的电话上]
int first = firstIndex(nums, 0, nums.length, target);
int last = lastIndex(nums, 0, nums.length, target);`
由于第三个参数引用了数组的最右索引,因此nums.length太高,因为该数组基于0。当寻找比最右边的元素大的东西时,我用您的代码复制了jdoodle上的错误,并将第一行中的nums.length更改为nums.length-1将错误推入了第二个调用。在第二个调用中用nums.length-1替换nums.length使其完全消失。
单击https://www.geeksforgeeks.org/binary-search/处的Java选项卡,您可以看到它们使用n -1。