Finding first and last occurrence of an element using BinarySearch

Question

I can find the first occurrence efficiently but I'm having trouble finding the last occurrence. The answer I get for the last occurrence of the element is always the correct index plus one.

Here is my code:

class FirstAndLastOccurence{

    public static int first(int[] arr, int n, int x){
        int left = 0;
        int right = n-1;
        int res = -1;

        while(left <= right){
            int mid = left + (right-left)/2;

            if(x < arr[mid])
                right = mid-1;
            if(x > arr[mid])
                left = mid+1;
            else{
                res = mid;
                right = mid-1;
            }
        }

        return res;
    }

    public static int last(int[] arr, int n, int x){
        int left = 0;
        int right = n-1;
        int res = -1;

        while(left <= right){
            int mid = left + (right-left)/2;
            
            if(x < arr[mid])
                right = mid-1;
            if(x > arr[mid])
                left = mid+1;
            else{
                res = mid;
                left = mid+1;
            }
        }

        return res;
    }

    public static void main(String[] args){
        int[] arr = new int[]{2, 4, 10, 10, 10, 10, 56, 71, 90};
        System.out.println(first(arr, arr.length, 10));
        System.out.println(last(arr, arr.length, 10));
    }
}

Output:

2
6

The first output is correct while my last output is wrong, as it should have been 5. The code I'm trying to follow is here (the code is not exactly the same, I'm implementing the binary search in a more familiar way to me personally).

Sindhura Gudarada · Accepted Answer · 2020-08-27 16:13:00Z

2

You have added both the if statements and else statement at the last which gets executed only for the second if statement which is incorrect. Please find the below code which is working and giving the correct answer.

public static int last(int[] arr, int n, int x){
    int left = 0;
    int right = n-1;
    int res = -1;

    while(left <= right){
        int mid = left + (right-left)/2;

        if(x < arr[mid])
            right = mid-1;
        else if(x > arr[mid])
            left = mid+1;
        else{
            res = mid;
            left = mid+1;
        }
    }

    return res;
}

answered Aug 27, 2020 at 16:13

Sindhura Gudarada

1047 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Finding first and last occurrence of an element using BinarySearch

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related