首页 > 代码库 > Search in Rotated Sorted Array
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.
思路：虽然链表被rotate了，但还是由有序序列构成，因此考虑使用二分查找。
若A[start]<A[end]，则A(start:end)由单个有序序列组成，直接使用二分查找。
若A[start]>A[end]，则A(start:end)由两个有序序列组成：
若A[middle]>=A[start]，则A[middle]来自第一个有序序列；若A[middle]<=A[end]，则A[middle]来自第二个有序序列；
若target>=A[start]，则target来自第一个有序序列；若target<=A[end]，则target来自第二有序序列。
首先确定middle和target的位置，然后调整start或end。
1 class Solution { 2 public: 3 int search( int A[], int n, int target ) { 4 int start = 0, end = n-1; 5 while( start <= end ) { 6 int middle = ( start + end ) / 2; 7 if( A[start] < A[end] ) { 8 if( A[middle] == target ) { return middle; } 9 if( A[middle] < target ) {10 start = middle + 1;11 } else {12 end = middle - 1;13 }14 } else {15 if( A[middle] == target ) { return middle; }16 if( A[middle] < target ) {17 if( A[middle] < A[start] && target >= A[start] ) {18 end = middle - 1;19 } else {20 start = middle + 1;21 }22 } else {23 if( A[middle] >= A[start] && target < A[start] ) {24 start = middle + 1;25 } else {26 end = middle - 1;27 }28 }29 }30 }31 return -1;32 }33 };
Search in Rotated Sorted Array
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。