Sunday, December 2, 2012

How to Get the Index of an Element in a Circular Buffer

Problem: Get the index of a particular element in a circular buffer, e.g.
Array: 7 8 9 0 1 2 3 4 5 6
search(0) --> index 3
search(6) --> index 9
public class CircularBinarySearch {
    // return -1 if not found
    private static int getIndex(int[] array, int value) {
        int minIdx = findMinIndex(array);
        return binarySearch(array, value, minIdx, array.length-1+minIdx, minIdx);
    }
    
    private static int binarySearch(int[] array, int value, int lo, int hi, int minIdx) {
        if (lo > hi) {
            return -1;
        }
        int mid = (lo + hi) / 2;
        int midIdx = getRealIndex(array.length, mid, minIdx);
        if (array[midIdx] == value) {
            return midIdx;
        } else if (array[midIdx] > value) {
            return binarySearch(array, value, lo, mid-1, minIdx);
        } else if (array[midIdx] < value) {
            return binarySearch(array, value, mid+1, hi, minIdx);
        }
        return -1;
    }
    
    private static int getRealIndex(int arrayLength, int idx, int minIdx) {
        if (idx >= arrayLength) {
            return idx - arrayLength;
        }
        return idx;
    }
    
    private static int findMinIndex(int[] array) {
        int minIdx = array[0];
        for (int i = 1; i < array.length; i++) {
            if (array[i] < array[minIdx]) {
                minIdx = i;
            }
        }
        return minIdx;
    }
    
    public static void main(String[] args) {
        int[] array = new int[10];
        array[0] = 7;
        array[1] = 8;
        array[2] = 9;
        array[3] = 0;
        array[4] = 1;
        array[5] = 2;
        array[6] = 3;
        array[7] = 4;
        array[8] = 5;
        array[9] = 6;
        
        // verify it
        for (int i = 0; i < array.length; i++) {
            System.out.println(array[i] + " --> " + getIndex(array, array[i]));
        }
        System.out.print("120 --> " + getIndex(array, 120));
    }
}

No comments:

Post a Comment