Searching an array by value and index

Question

I have a sorted array of integers, on which I want to perform searching. This array can have repeated values. If I search for an element that is repeated, then it should return the index of the first instance of the element.

If I use the Arrays.binarySearch(), then it doesn't necessarily give out the index of the first instance of the element searched. Example can be seen here:

int[] A = {10,20,21,24,24,24,24,24,30,40,45} ;
int idx = Arrays.binarySearch(A,24) ;

Where, idx will be 5. I want it to be 3. I solved this problem earlier by making a class Pair like :

class Pair implements Comparable<Pair>
{
    int value, index ;
    Pair(int v,int i)
    {
        this.value = v ;
        this.index = i ;
    }
    @Override
    public int compareTo(Pair p)
    {
        if(p.value<this.value)
            return 1 ;
        else if(p.value>this.value)
            return -1 ;
        else 
        {
            if(p.index<this.index)
                return 1 ;
            else if(p.index>this.index)
                return -1 ;
            else return 0 ;
        }
    }
}

Which when searched with Collections.binarySearch(new Pair(24,Integer.MIN_VALUE)) (for a list of Pairs) would return a 3. The code then would be:

int[] A = {10,20,21,24,24,24,24,24,30,40,45} ;

        List<Pair> L = new ArrayList<Pair>() ;

        for(int i=0;i<A.length;i++)
        {
            L.add(new Pair(A[i],i)) ;
        }
        int idx = Collections.binarySearch(L,new Pair(24,Integer.MIN_VALUE)) ;
        if(idx<0) idx = -idx-1 ;
        System.out.println(idx) ;

Pair works like this: It has two variables value and index, which are the value of the element of the sorted array, and index of the element in the array. The compareTo method is overridden in order to allow Collections.binarySearch() to perform comparisons. The comparisons can be defined like this:

• If the current value is greater or less, then the order is decide by value.
• If values are the same, then order is decided using index.

My question is, can this be done in a less messy way? Anything that is shorter, would be greatly appreciated!

Answer 1

Have a look at below piece of code. Made changes to original binary search code: l and r are the left and right range respectively

public static int binarySearch(int[] arr, int num, int l,int r) {
    int mid = (l+r)/2;
    if(arr[mid] == num && (mid>0&& arr[mid-1]!=num) || mid==0) {            
        return mid;
    }       
    else if(arr[mid] > num || (mid > l && arr[mid] == num && arr[mid-1] == num)) {
        return binarySearch(arr, num, l, mid);
    }else {
        return binarySearch(arr, num, mid, r);
    }
}