首页 > 代码库 > LeetCode: Search in Rotated Sorted Array

LeetCode: Search in Rotated Sorted Array

2024-07-21 01:04:04   223人阅读

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


联系
我们