將一個數組排序，然後進行旋轉，從該陣列中尋找指定元素。

例如arr = [16, 19, 3, 5, 8, 10, 21, 25]，排序後變成arr1 = [3, 5, 8, 10, 16, 19, 21, 25]，向左旋轉4個單位，arr2 = [16, 19, 21, 25, 3, 5, 8, 10]，設計算法查詢元素5的位置。

旋轉陣列

原理找到中間點 mid = (lo +hi) / 2IF key就是中間點，那麼返回midELSE IF arr[lo..mid]是排好序的，分兩種情況

a) IF key值在arr[lo]到arr[mid]之間，那麼繼續在arr[lo..mid]中查詢

b) ELSE 在arr[mid+1..hi]裡面查詢元素

ELSE arr[mid+1..hi]是排好序的，分兩種情況

a) IF key值在arr[mid+1]到arr[hi]之間，那麼繼續在arr[mid+1..hi]之間查詢

b) ELSE繼續在arr[lo..mid]之間查詢

實現

public class ArraySearch {    static int search(int arr[], int lo, int hi, int key) {        if (lo > hi)            return -1;        int mid = (lo + hi) / 2;        if (arr[mid] == key)            return mid;        // If arr[lo..mid] first subarray is sorted.        if (arr[lo] <= arr[mid]) {            // As this subarray is sorted, we can quickly check if            // key lies in half or other half.            if (key >= arr[lo] && key <= arr[mid])                return search(arr, lo, mid - 1, key);            // If key not lies in first half subarray,            // such that we an quickly check if key lies            // in other half.            return search(arr, mid + 1, hi, key);        }        // If arr[lo..mid] first subarray is not sorted,        // then arr[mid+1...hi] must be sorted subarray.        if (key >= arr[mid] && key <= arr[hi])            return search(arr, mid + 1, hi, key);        // arr[lo..mid] first subarray is not sorted,        // and key lies in first half subarray.        return search(arr, lo, mid - 1, key);    }    public static void main(String args[]) {        int arr[] = {16, 19, 21, 25, 3, 5, 8, 10};        int key = 5;        System.out.println("Index: " + search(arr, 0, arr.length - 1, key));    }}

輸出

Index: 5