package Sorting_Searching;
/**
* Given a sorted array of n integers that has been rotated an unknown number of
* times, give an O(log n) algorithm that finds an element in the array. You may
* assume that the array was originally sorted in increasing order.
*
* EXAMPLE:
*
* Input: find 5 in array (15 16 19 20 25 1 3 4 5 7 10 14)
*
* Output: 8 (the index of 5 in the array)
*
* 译文：
*
* 一个数组有n个整数，它们排好序(假设为升序)但被旋转了未知次， 即每次把最右边的数放到最左边。给出一个O(log n)的算法找到特定的某个元素。
*
* 例子：
*
* 输入：在数组(15 16 19 20 25 1 3 4 5 7 10 14)中找出5
*
* 输出：8（5在数组中的下标）
*
*/
public class S11_3 {
public static void main(String[] args) {
int[] a = { 2, 3, 2, 2, 2, 2, 2, 2, 2, 2 };
System.out.println(search(a, 0, a.length - 1, 2));
System.out.println(search(a, 0, a.length - 1, 3));
System.out.println(search(a, 0, a.length - 1, 4));
System.out.println(search(a, 0, a.length - 1, 1));
System.out.println(search(a, 0, a.length - 1, 8));
}
public static int search(int a[], int left, int right, int x) {
int mid = (left + right) >
> 1;
if(x == a[mid]){ // 找到
return mid;
}
if(left > right){
return -1;
}
if(a[left] < a[mid]){ // 比如 Arrayl: {10, 15, 20, 0, 5}，找5
if(x>=a[left] && x<=a[mid]){
return search(a, left, mid-1, x);
}else{
return search(a, mid+1, right, x);
}
}else if(a[left] > a[mid]){ // 比如：Array2: {50, 5, 20, 30, 40}，找5
if(a[mid]<=x && x<=a[right]){
return search(a, mid+1, right, x);
}else{
return search(a, left, mid-1, x);
}
}else if(a[left] == a[mid]){ // 比如：{2, 2, 2, 3, 4, 2}
if(a[mid] != a[right]){
return search(a, mid+1, right, x);
}else{
int result = search(a, left, mid-1, x);
if(result == -1){
result = search(a, mid+1, right, x);
}
return result;
}
}
return -1;
}
}