Это пример, который работает в Java. Поскольку это отсортированный массив, вы воспользуетесь этим и запустите бинарный поиск, однако его необходимо немного изменить, чтобы он соответствовал позиции стержня.
Метод выглядит так:
private static int circularBinSearch ( int key, int low, int high )
{
if (low > high)
{
return -1; // not found
}
int mid = (low + high) / 2;
steps++;
if (A[mid] == key)
{
return mid;
}
else if (key < A[mid])
{
return ((A[low] <= A[mid]) && (A[low] > key)) ?
circularBinSearch(key, mid + 1, high) :
circularBinSearch(key, low, mid - 1);
}
else // key > A[mid]
{
return ((A[mid] <= A[high]) && (key > A[high])) ?
circularBinSearch(key, low, mid - 1) :
circularBinSearch(key, mid + 1, high);
}
}
Теперь, чтобы облегчить любые заботы, вот небольшой класс, который проверяет алгоритм:
public class CircularSortedArray
{
public static final int[] A = {23, 27, 29, 31, 37, 43, 49, 56, 64, 78,
91, 99, 1, 4, 11, 14, 15, 17, 19};
static int steps;
// ---- Private methods ------------------------------------------
private static int circularBinSearch ( int key, int low, int high )
{
... copy from above ...
}
private static void find ( int key )
{
steps = 0;
int index = circularBinSearch(key, 0, A.length-1);
System.out.printf("key %4d found at index %2d in %d steps\n",
key, index, steps);
}
// ---- Static main -----------------------------------------------
public static void main ( String[] args )
{
System.out.println("A = " + Arrays.toString(A));
find(44); // should not be found
find(230);
find(-123);
for (int key: A) // should be found at pos 0..18
{
find(key);
}
}
}
Это даст вам вывод:
A = [23, 27, 29, 31, 37, 43, 49, 56, 64, 78, 91, 99, 1, 4, 11, 14, 15, 17, 19]
key 44 found at index -1 in 4 steps
key 230 found at index -1 in 4 steps
key -123 found at index -1 in 5 steps
key 23 found at index 0 in 4 steps
key 27 found at index 1 in 3 steps
key 29 found at index 2 in 4 steps
key 31 found at index 3 in 5 steps
key 37 found at index 4 in 2 steps
key 43 found at index 5 in 4 steps
key 49 found at index 6 in 3 steps
key 56 found at index 7 in 4 steps
key 64 found at index 8 in 5 steps
key 78 found at index 9 in 1 steps
key 91 found at index 10 in 4 steps
key 99 found at index 11 in 3 steps
key 1 found at index 12 in 4 steps
key 4 found at index 13 in 5 steps
key 11 found at index 14 in 2 steps
key 14 found at index 15 in 4 steps
key 15 found at index 16 in 3 steps
key 17 found at index 17 in 4 steps
key 19 found at index 18 in 5 steps