在排好序的陣列中使用二分法(Binary search)進行元素查詢，時間複雜度是O(logn)，但是如果將陣列進行旋轉，比如1 2 3 4 5變成 3 4 5 1 2，那麼怎麼在O(logn)的時間複雜度中進行查詢呢？

部分排序的陣列

例子

輸入 arr[] = {5, 6, 7, 8, 9, 10, 1, 2, 3}

key = 3

輸出 8

輸入 arr[] = {30, 40, 50, 10, 20}

key = 10

輸出 3

方法

最直接的想法就是找到旋轉點(pivot point)，然後分別對兩邊使用二分法進行查詢。

旋轉點的定義是下一個元素比上一個元素小，使用二分法可以將旋轉點找到。根據旋轉點將陣列拆分為兩個子陣列。兩個陣列分別用二分法進行查詢。

實現

public class ArraySearch {    /**     * 查詢分割點下標     *     * @param arr  陣列     * @param low  起始     * @param high 結束     * @return　查詢的下標     */    static int findPivot(int arr[], int low, int high) {        // base case        if (high < low)            return -1;        else if (high == low)            return low;        int mid = (low + high) / 2;        if (mid < high && arr[mid] > arr[mid + 1])            return mid; // 前一個元素比後一個元素大        if (mid > low && arr[mid] < arr[mid - 1])            return mid - 1;        // 最小比中間的大說明分割點在其中        if (arr[low] >= arr[mid])            return findPivot(arr, low, mid - 1);        return findPivot(arr, mid + 1, high);    }    static int binarySearch(int arr[], int low, int high, int key) {        if (high < low)            return -1;        int mid = (low + high) / 2;        if (key == arr[mid])            return mid;        if (key > arr[mid])            return binarySearch(arr, mid + 1, high, key);        else            return binarySearch(arr, low, mid - 1, key);    }    static int pivotedBinarySearch(int arr[], int key) {        int pivot = findPivot(arr, 0, arr.length - 1);        if (pivot == -1)            return binarySearch(arr, 0, arr.length - 1, key);        // If we found a pivot, then first compare with pivot and        // then search in two subarrays around pivot.        if (arr[pivot] == key)            return pivot;        if (arr[0] <= key)            return binarySearch(arr, 0, pivot - 1, key);        else            return binarySearch(arr, pivot + 1, arr.length - 1, key);    }    public static void main(String args[]) {        int arr[] = {5, 6, 7, 8, 9, 10, 1, 2, 3};        int key = 3;        // 輸出8        System.out.println("Index of the element is: " +                pivotedBinarySearch(arr, key));    }}