[LeetCode] Search in Rotated Sorted Array

Suppose a sorted array is rotated at some pivot unknown to you beforehand.

(i.e.,0 1 2 4 5 6 7might become4 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.

这道题可以和之前那个rotated sorted array的思路一样，cut haof of array every time来找target。

然后就没啥可说了，单独写一个find()method比较方便。

只是要注意这里的if的条件就要细致的多了，要多考虑，最好画个图（……我就画了，因为浆糊了不画图哈哈哈）

代码如下。~

public class Solution {    public int search(int[] nums, int target) {        int len=nums.length;        return find(nums,0,len-1,target);            }    public int find(int[] nums,int start,int end,int target){        if(start>end){            return -1;        }        int mid=(start+end)/2;        if(nums[mid]==target){            return mid;        }        if((target<nums[mid]&&target>=nums[start])||(target<nums[mid]&&nums[mid]<nums[start])||(target>=nums[start]&&nums[start]>nums[mid])){            return find(nums,start,mid-1,target);        }        return find(nums,mid+1,end,target);    }}