你的位置:首页 > Java教程

[Java教程][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 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.

 

     这道题可以和之前那个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);  }}