CODEWITHSUNDEEP
javabinary-search
coderfromhell
coderfromhell

Reputation: 455

Finding first and last occurrence of an element using BinarySearch

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).

Upvotes: 0

Views: 658

Answers (1)

Sindhura Gudarada
Sindhura Gudarada

Reputation: 104

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

Upvotes: 2

Related Questions