81. Search in Rotated Sorted Array II

Problem

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 Search in Rotated Sorted Array, where nums may contain duplicates.
• Would this affect the run-time complexity? How and why?

Problem Summary

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand. (For example, the array [0,0,1,2,2,5,6] might become [2,5,6,0,0,1,2] ).

Write a function to determine whether a given target value exists in the array. If it exists, return true; otherwise, return false.

Follow up:

• This is an extension of Search in Rotated Sorted Array; in this problem, nums may contain duplicates.
• Would this affect the program's time complexity? How would it affect it, and why?

Solution Approach

• Given an array that was originally sorted in ascending order and contains duplicate numbers. Now a random sorted segment from the end has been moved to the front of the array, forming two sorted subsequences at the front and back. Search for a number in such an array and design an O(log n) algorithm. If found, output true; if not found, output false.
• This problem is an enhanced version of Problem 33. The implementation code is exactly the same; only the output has changed. This problem outputs true and false. For the detailed approach, see Problem 33.

Code

package leetcode

func search(nums []int, target int) bool {
	if len(nums) == 0 {
		return false
	}
	low, high := 0, len(nums)-1
	for low <= high {
		mid := low + (high-low)>>1
		if nums[mid] == target {
			return true
		} else if nums[mid] > nums[low] { // in the interval with larger values
			if nums[low] <= target && target < nums[mid] {
				high = mid - 1
			} else {
				low = mid + 1
			}
		} else if nums[mid] < nums[high] { // in the interval with smaller values
			if nums[mid] < target && target <= nums[high] {
				low = mid + 1
			} else {
				high = mid - 1
			}
		} else {
			if nums[low] == nums[mid] {
				low++
			}
			if nums[high] == nums[mid] {
				high--
			}
		}
	}
	return false
}