0081-search-in-rotated-sorted-array-ii.adoc

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?

解题思路

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

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

参考资料

1. 搜索旋转排序数组 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?

link:{sourcedir}/_0081_SearchInRotatedSortedArrayII.java[role=include]