首页 > 代码库 > [Leetcode] Search in Rotated Sorted Array
[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.
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 else16 start=mid+1;17 }else if(A[mid]<=A[end]){18 if(A[mid]<=target&&target<=A[end]){19 start=mid+1;20 }else21 end=mid-1;22 }23 }24 return -1;25 }26 }
Note:
黄色部分，不要少加了=号，这样在某些情况下（比如[1], 0的情况）会进入不了判断条件里，导致start和end无法改变，超时。
[Leetcode] Search in Rotated Sorted Array
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。