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.
Solution:
1 public class Solution { 2 public int search(int[] A, int target) { 3 if(A.length<=0) 4 return 0; 5 int start=0; 6 int end=A.length-1; 7 while(start<=end){ 8 int mid=(start+end)/2; 9 if(A[mid]==target) 10 return mid; 11 if(A[mid]>=A[start]){ 12 if(A[mid]>=target&&target>=A[start]){ 13 end=mid-1; 14 } 15 else 16 start=mid+1; 17 }else if(A[mid]<=A[end]){ 18 if(A[mid]<=target&&target<=A[end]){ 19 start=mid+1; 20 }else 21 end=mid-1; 22 } 23 } 24 return -1; 25 } 26 }
Note:
黄色部分，不要少加了=号，这样在某些情况下（比如[1], 0的情况）会进入不了判断条件里，导致start和end无法改变，超时。
[Leetcode] Search in Rotated Sorted Array
原文：http://www.cnblogs.com/Phoebe815/p/4100950.html