直接上代码
/**
* Created by lvhao on 2017/6/30.
* Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand. (i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2). You are given a target value to search. If found in the array return its index, otherwise return -1. You may assume no duplicate exists in the array.
思路是目标值肯定在一个升序子序列中（可能子序列很短，但是肯定存在），目标就是找到这个子序列然后用二分法找到值
找目标序列的时候也是用二分法，判断的依据是mid值比fin值大的话说明左边是升序，小的话，右边是升序，然后在利用升序序列的的
首尾值判断目标值是否在里边，在里边就用二分法找值，不在里边就改变fin或者sta值，继续循环找，注意二分法的时候while的判断
条件是sta<= fin,如果没有=的话，两个数的情况判断不出来。
*/
public class Q33SearchRotatedArray {
public static void main(String[] args) {
int[] nums = new int[]{3,1};
int target = 1;
int res = search(nums,target);
System.out.println(res); }
public static int search(int[] nums, int target) {
int len = nums.length;
//判断特殊情况
if(len == 1 && nums[0] == target)
{
return 0;
}
int sta = 0,fin = len-1,mid,index = -1;
//注意等号
while(sta <= fin)
{
mid = (sta + fin)/2;
if(nums[mid] < nums[fin])
{
if(target <= nums[fin] && target >= nums[mid])
{
index = binarySearch(nums,mid,fin,target);
//找到值之后立即break
break;
} else
fin = mid -1;
}
else
{
if(target <= nums[mid] && target >= nums[sta])
{
index = binarySearch(nums,sta,mid,target);
break;
} else
sta = mid + 1;
}
}
return index;
}
public static int binarySearch(int[] nums,int sta,int fin,int target)
{
int mid,index = -1;
//注意等号
while (sta <= fin)
{
mid = (sta + fin)/2;
if(target == nums[mid])
{
index = mid;
break;
}
else if (target < nums[mid])
fin = mid-1;
else
sta = mid+1;
}
return index;
}
}