LeetCode 33.Search in Rotated Sorted Array (搜索旋转排序数组)

旧城等待， 2022-05-11 04:06 126阅读 0赞

题目描述：

假设按照升序排序的数组在预先未知的某个点上进行了旋转。

( 例如，数组 `[0,1,2,4,5,6,7]` 可能变为 `[4,5,6,7,0,1,2]`)。

搜索一个给定的目标值，如果数组中存在这个目标值，则返回它的索引，否则返回 `-1` 。

你可以假设数组中不存在重复的元素。

你的算法时间复杂度必须是 *O*(log *n*) 级别。

示例：

输入: nums = [4,5,6,7,0,1,2], target = 0
    输出: 4

输入: nums = [4,5,6,7,0,1,2], target = 3
    输出: -1

Accepted C++ Solution:

class Solution {
    public:
        int search(vector<int>& nums, int target) {
            int n  = nums.size();
            int lo=0,hi=n-1;
            
            // find the index of the smallest value using binary search.
            // Loop will terminate since mid < hi, and lo or hi will shrink by at least 1.
            // Proof by contradiction that mid < hi: if mid==hi, then lo==hi and loop would have been terminated.
            while(lo<hi){
                int mid=(lo+hi)/2;
                if(nums[mid]>nums[hi]) lo=mid+1;
                else hi=mid;
            }                   //寻找最小的元素
            
            // lo==hi is the index of the smallest value and also the number of places rotated.
            int rot=lo;
            lo=0;hi=n-1;
            
            // The usual binary search and accounting for rotation.
            while(lo<=hi){
                int mid=(lo+hi)/2;
                int realmid=(mid+rot)%n;        //真正的中位数
                if(nums[realmid]==target)   return realmid;
                if(nums[realmid]<target)    lo=mid+1;
                else    hi=mid-1;
            }
            return -1;
        }
    };

首先找到数组中最小的元素,最小的元素位置就是旋转的位置rot。

然后进行二分查找时，真正的中间位置 readmid = (mid+rot) % n;

(旋转就相当于循环右移了rot位,所以实际中间位置就为 (mid + rot) % n );

按照readmid位置的元素查找目标值。