LeetCode: 81. Search in Rotated Sorted Array II

友情支持

如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜

支付宝

有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。

wx jikerizhi

公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。

81. Search in Rotated Sorted Array II

LeetCode - Search in Rotated Sorted Array II

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.

(i.e., [0,0,1,2,2,5,6] might become [2,5,6,0,0,1,2]).

You are given a target value to search. If found in the array return true, otherwise return false.

Example 1:

Input: nums = [2,5,6,0,0,1,2], target = 0
Output: true

Example 2:

Input: nums = [2,5,6,0,0,1,2], target = 3
Output: false

Follow up:

This is a follow up problem to 33. Search in Rotated Sorted Array, where nums may contain duplicates.
Would this affect the run-time complexity? How and why?

解题思路

这道题的关键是先确定哪部分有序，然后判断目标值是否在有序区间内，如果没有则再另外一部分内。

另外，需要注意的就是对重复值的处理。如果左边的值和中间值相等，直接让左边下标向前移动一下，简单有效。

参考资料

搜索旋转排序数组 II - 搜索旋转排序数组 II - 力扣（LeetCode）

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.

(i.e., [0,0,1,2,2,5,6] might become [2,5,6,0,0,1,2]).

You are given a target value to search. If found in the array return true, otherwise return false.

Example 1:

Input: nums = [2`,5,6,0,0,1,2]`, target = 0
Output: true

Example 2:

Input: nums = [2`,5,6,0,0,1,2]`, target = 3
Output: false

Follow up:

This is a follow up problem to <a href="/problems/search-in-rotated-sorted-array/description/">Search in Rotated Sorted Array</a>, where nums may contain duplicates.
Would this affect the run-time complexity? How and why?

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
/**
 * Runtime: 0 ms, faster than 100.00% of Java online submissions for Search in Rotated Sorted Array II.
 * Memory Usage: 38.6 MB, less than 88.73% of Java online submissions for Search in Rotated Sorted Array II.
 *
 * Copy from: https://leetcode-cn.com/problems/search-in-rotated-sorted-array-ii/solution/zai-javazhong-ji-bai-liao-100de-yong-hu-by-reedfan/[搜索旋转排序数组 II - 搜索旋转排序数组 II - 力扣（LeetCode）]
 */
public boolean search(int[] nums, int target) {
    if (Objects.isNull(nums) || nums.length == 0) {
        return false;
    }
    int left = 0, right = nums.length - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) {
            return true;
        }
        if (nums[left] == nums[mid]) {
            left++;
            continue;
        }
        if (nums[left] < nums[mid]) {
            if (nums[left] <= target && target < nums[mid]) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        } else {
            if (nums[mid] < target && target <= nums[right]) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
    }
    return false;
}