indexoutofboundsexceptionjava.lang.classjava

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


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;
}

}

Here is my solution using binary search. It can be accepted when I run the code but cannot be submitted. There is an ArrayIndexOutOfBoundsException at if (nums[pivot] == target). I couldn't understand why this happened. And I looked into solutions. Most of the solution using this way. I don't know how to get rid of this error. Can somebody help me explain this???? Thank you so much!!!!

enter image description here


Solution

  • I am pretty sure the issue is with your calling`

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

    Since the third parameter refers to the rightmost index of the array, nums.length is 1 too high because the array is 0-based. I duplicated the error on jdoodle with your code when looking for something bigger than the rightmost element, and changing nums.length to nums.length-1 in the first line pushed the error into the second call. Replacing nums.length with nums.length-1 in the second call made it go away entirely.

    Clicking the java tab at https://www.geeksforgeeks.org/binary-search/ you can see they use n -1.