Use a Binary Search on an int array sorted in descending order

Question

import java.util.*;
import java.io.*;
import java.util.Arrays;
import java.util.Collections;
import org.apache.commons.lang3.ArrayUtils;
@SuppressWarnings("unused")
public class Tester {
    public static void main(String args[]){
        int i[] = {-7, 15, 21, 22, 43, 49, 51, 67, 81, 84, 89, 95, 97};
        ArrayUtils.reverse(i);
        System.out.println(binarySearch(i, 22));
        System.out.println(binarySearch(i, 89));
        System.out.println(binarySearch(i, -100));
        System.out.println(binarySearch(i, 72));
        System.out.println(binarySearch(i, 102));
    }
    private static int binarySearch(int a[], int srchVal){
        int lb = 0;
        int ub = a.length - 1;

        while(lb <= ub){
            int mid = (lb + ub)/2;
            if(a[mid] == srchVal){
                return mid;
            }
            else if(srchVal > a[mid]){
                lb = mid + 1;
            }
            else{
                ub = mid - 1;
            }
         }
        return -1;
    }
}

For an assignment in class I need to modify the BinarySearch method so that it will work properly with the reversed array. But I can't figure out how I'm supposed to modify it.

Answer 1

If the array is sorted in descending order, binary search can still work if you reverse the sense of all value comparisons performed by the search algorithm.

The equals case is still fine, but you can reverse the comparison made in the else if to a <. The else doesn't need to be modified, because the else if change means the else block will now represent the > condition.

Answer 2

Binary search makes the assumption the data is ordered. If that's the case, than one knows if the value of the selected index (mid) is less than the value, the value must be in the range 0..mid-1 and vice versa.

In case the array is ordered in reverse, one knows that if the value is less, then one must search in the second part. The only thing you must modify is the condition in the else if:

else if(srchVal < a[mid]){ //change < to >
    lb = mid + 1;
}

That said, one better makes the method a bit more generic so one can make the comparator more generic as well:

private static<T> int binarySearch(T[] a, Comparator<T> c, T srchVal){
    int lb = 0;
    int ub = a.length - 1;

    while(lb <= ub){
        int mid = (lb + ub)/2;
        int ci = c.compare(a[mid],srchVal);
        if(ci == 0){
            return mid;
        }
        else if(ci < 0){
            lb = mid + 1;
        }
        else{
            ub = mid - 1;
        }
     }
    return -1;
}

In case you provide a reversed array, you only need to provide a Comparator<T> that returns -val with val the comparator for the original array.