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