首页 > 代码库 > LeetCode: Search in Rotated Sorted Array
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.
地址:https://oj.leetcode.com/problems/search-in-rotated-sorted-array/
算法:将二分查找稍微改进一下就可以了。首先,我们把旋转后的数组分为上部分和下部分,比如题目例子中(4 5 6 7)为上部分,(0 1 2)为下部分,注意上部分和下部分都有可能为空。如果中间节点等于目标值,返回;否则,若中间节点大于尾节点,说明中间节点处于上部分,此时在分三种情况讨论,具体可以看代码;若中间节点小于等于尾节点,说明中间节点处于下部分,此时也可以分三种情况,具体看代码。代码:
1 class Solution { 2 public: 3 int search(int A[], int n, int target) { 4 if(n < 1) return -1; 5 int begin = 0, end = n-1; 6 int mid = 0; 7 while(begin <= end){ 8 mid = (begin + end) >> 1; 9 if(A[mid] == target){10 return mid;11 }12 if(A[mid] > A[end]){13 if(A[mid] < target)14 begin = mid + 1;15 else if(target > A[end]){16 end = mid - 1;17 }else{18 begin = mid + 1;19 }20 }else{21 if(A[mid] > target){22 end = mid - 1;23 }else if(target <= A[end]){24 begin = mid + 1;25 }else{26 end = mid - 1;27 }28 }29 }30 return -1;31 }32 };
第二题:
Follow up for "Search in Rotated Sorted Array":
What if duplicates are allowed?
Would this affect the run-time complexity? How and why?
Write a function to determine if a given target is in the array.
地址:https://oj.leetcode.com/problems/search-in-rotated-sorted-array-ii/
算法:跟上一题比,多了一个条件:数组中的元素有可能不唯一。同样把bottom和top之间分为上部分和下部分。首先,如果mid就是要找的元素,直接返回;否则,如果top的元素大于bottom的元素,说明bottom和top之间的元素是有序的,则按正常的二分查找即可。否则如果mid大于bottom,则mid位于上部分,所以分三种情况讨论;如果mid小于bottom,则mid为于下部分,所以也分三种情况讨论;剩下mid等于bottom的情况,如果此时mid大于top的话,那说明bottom和mid之间的所有元素都相等,所以都不等与target,故bottom之间设为mid+1;剩下的情况直接线性查找。代码:
1 class Solution { 2 public: 3 bool search(int A[], int n, int target) { 4 if(!A || n < 1){ 5 return false; 6 } 7 int bottom = 0; 8 int top = n - 1; 9 while(bottom <= top){10 int mid = (bottom + top) / 2;11 if(A[mid] == target){12 return true;13 }14 if(A[top] > A[bottom]){15 if(A[mid] < target)16 bottom = mid + 1;17 else18 top = mid - 1;19 }else{20 if(A[mid] > A[bottom]){ 21 if(A[mid] < target)22 bottom = mid + 1;23 else if(A[bottom] <= target)24 top = mid - 1;25 else26 bottom = mid + 1;27 }else if(A[mid] < A[bottom]){28 if(A[mid] > target)29 top = mid - 1;30 else if(A[top] >= target)31 bottom = mid + 1;32 else33 top = mid - 1;34 }else{35 if(A[top] < A[mid]){36 bottom = mid + 1;37 }else{38 for(int i = bottom; i <= top; ++i){39 if(A[i] == target){40 return true;41 }42 }43 return false;44 }45 }46 }47 }48 return false;49 }50 };
LeetCode: Search in Rotated Sorted Array