问题描述

Suppose an array sorted in ascending order 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.

Your algorithm's runtime complexity must be in the order of O(log n).

Example 1:

Input: nums = [4,5,6,7,0,1,2], target = 0

Output: 4

Example 2:

Input: nums = [4,5,6,7,0,1,2], target = 3

Output: -1

参考答案

class Solution {

public:

    int search(vector<int>& nums, int target) {

        if(nums.size() == ) return -;

        int l = ;

        int r = nums.size()-;

        while(l<r){

            int mid = (l+r)>>;

            if(nums[l]<=nums[mid]){

                if(target<=nums[mid] && target >= nums[l]) r = mid;

                else l = mid +;

            }else if(nums[mid]<nums[r]){

                if(target>nums[mid] && target <= nums[r]) l = mid +;

                else r = mid;

            }

        }

        if(target == nums[l]) return r;

        return -;

    }

};

答案描述

由于不知道序列是否有序，因此在进行二分搜索的时候，需要先确定在什么区间：

1. 低位< 中位：意味着从低位到中位，一定是有序的。如果循环的连接点，没有过中位，那么中位海拔更低，低位海拔更高，这个时候，有序的数列在，

2. 中位<高位：之间，这一段里面就是有序的，因此可以在这个区间内进行搜索。

宗旨，时刻保持有序。

巴特西

LC 33. Search in Rotated Sorted Array

问题描述

参考答案

答案描述

最新文章

热门文章