描述
輸入一個(gè)遞增排序的數(shù)組（元素不重復(fù)）的一個(gè)旋轉(zhuǎn)（次數(shù)不詳）惯雳，找出某個(gè)元素.復(fù)雜度?O(lgn)已添。
輸入
第一行：N，數(shù)組的長(zhǎng)度
第二行：N個(gè)整數(shù)滥酥，作為數(shù)組的元素，空格分開
第三行：要查找的關(guān)鍵字K
輸出
關(guān)鍵字K的下標(biāo)畦幢，如果沒有找到坎吻，輸出-1
樣例輸入
5
6 1 2 3 4
1
樣例輸出
1
思路：
巧用二分法解題，可以先找出旋轉(zhuǎn)數(shù)組最小值(前邊詳細(xì)解釋過)宇葱，然后以最小值為軸瘦真，左右一定分別有序，在比較目標(biāo)與數(shù)組尾元素的大小黍瞧，判斷在左還是右進(jìn)行二分查找诸尽。
（Java代碼參考如下）
import java.util.Scanner;
public class Exam11_FindInRotaryArr {
public static void main(String[] args) {
int res = 0;
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] a = new int[n];
for(int i = 0; i < a.length; i++) {
a[i] = sc.nextInt();
}
int target = sc.nextInt();
if(target == a[minIndex(a)]) {
res = minIndex(a);
}else if(target > a[a.length-1]) {//在最小數(shù)左側(cè)做二分查找
res = binarySearch(a, 0, minIndex(a)-1, target);
}else if(target < a[a.length-1]) {//在最小數(shù)右側(cè)做二分查找
res = binarySearch(a, minIndex(a)+1, a.length-1, target);
}
System.out.println(res);
}
static int minIndex(int[] arr) {
int begin = 0;
int end = arr.length - 1;
if(arr[begin] <= arr[end]) return begin;
while(begin + 1 < end) {
int midIndex = begin + ((end - begin)>>1);
if(arr[begin] == arr[midIndex] || arr[end] == arr[midIndex]) {//特殊數(shù)組情況
int min = arr[0];
int mindex = 0;
for(int i = 0; i < arr.length; i++) {
if(arr[i] < min) {
min = arr[i];
mindex = i;
}
}
return mindex;
}
if(arr[begin] < arr[midIndex] ) {//左側(cè)有序
begin = midIndex;
}else {
end = midIndex;
}
}
return end;
}
static int binarySearch(int[] arr, int begin, int end, int target) {
int midIndex = begin + ((end - begin)>>1);
while(begin < end) {
if(target > arr[midIndex]) {
begin = midIndex + 1;
}else if(target < arr[midIndex]) {
end = midIndex - 1;
}else {
return midIndex;
}
}
return -1;
}
}
