描述
输入一个递增排序的数组（元素不重复）的一个旋转（次数不详），找出某个元素.复杂度 O(lgn)。
输入
第一行：N，数组的长度
第二行：N个整数，作为数组的元素，空格分开
第三行：要查找的关键字K
输出
关键字K的下标，如果没有找到，输出-1
样例输入
5
6 1 2 3 4
1
样例输出
1
思路：
巧用二分法解题，可以先找出旋转数组最小值(前边详细解释过)，然后以最小值为轴，左右一定分别有序，在比较目标与数组尾元素的大小，判断在左还是右进行二分查找。
（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]) {//在最小数左侧做二分查找
res = binarySearch(a, 0, minIndex(a)-1, target);
}else if(target < a[a.length-1]) {//在最小数右侧做二分查找
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]) {//特殊数组情况
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] ) {//左侧有序
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;
}
}
网友评论