Bitonic search

Given a bitonic array, we need to determine if a number is part of the array or not.

This is actually a triple binary search problem: finding the peak spot and then finding the number in the left and right subarrays.

public int search(final int[] a, final int x, final Comparator<Integer> comparator, int left, int right) {
    while (left < right) {
        int middle = left + (right - left) / 2;
        if (comparator.compare(a[middle], x) == 0) {
            return middle;
        } else {
            if (comparator.compare(a[middle], x) < 0) {
                right = middle - 1;
            } else {
                left = middle + 1;
            }
        }
    }
    return -1;
}

public int findPeak(final int[] a) {
    int left = 0;
    int right = a.length - 1;

    while (left < right) {
        int middle = left + (right - left) / 2;
        if (middle >= 1 && middle <= a.length - 2) {
            if (a[middle - 1] <= a[middle] && a[middle] <= a[middle + 1]) {
                left = middle + 1;
            } else {
                if (a[middle - 1] >= a[middle] && a[middle] >= a[middle - 1]) {
                    right = middle - 1;
                } else {
                    return middle;
                }
            }
        }
    }

    return -1;
}

public int bitonicSearch(final int[] a, final int x){
    int peak = findPeak(a);
    int elem = search(a, x, new Comparator<Integer>() {
        @Override
        public int compare(Integer o1, Integer o2) {
            return o1.compareTo(o2);
        }
    }, 0, peak);
    
    if(elem == -1){
        return search(a, x, new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2.compareTo(o1);
            }
        }, 0, peak);
    }
    
    return elem;
}
Advertisements