33. Search in Rotated Sorted Array

Problem

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

Problem Summary

Assume an array sorted in ascending order is rotated at some pivot unknown beforehand. (For example, the array [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2].) Search for a given target value. If the target value exists in the array, return its index; otherwise return -1. You may assume that there are no duplicate elements in the array.

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

Solution Approach

• Given an array that was originally sorted in ascending order and contains no duplicate numbers. But now a random ordered segment from the end has been moved to the front of the array, forming two ordered subsequences at the front and back. Search for a number in such an array and design an O(log n) algorithm. If found, output its index in the array; if not found, output -1.
• Since the array is basically ordered, although there is a "break point" in the middle, binary search can still be used to implement it. Now the front segment of the array contains relatively large values, and the rear segment contains relatively small values. If mid falls within the front interval with relatively large values, then there must be nums[mid] > nums[low]; if it falls within the rear interval with relatively small values, then nums[mid] ≤ nums[low]. If mid falls within the rear interval with relatively small values, then there must be nums[mid] < nums[high]; if it falls within the front interval with relatively large values, then nums[mid] ≤ nums[high]. There are also the cases nums[low] == nums[mid] and nums[high] == nums[mid], which can be handled separately. Finally, if found, output mid; if not found, output -1.

Code

package leetcode

func search33(nums []int, target int) int {
	if len(nums) == 0 {
		return -1
	}
	low, high := 0, len(nums)-1
	for low <= high {
		mid := low + (high-low)>>1
		if nums[mid] == target {
			return mid
		} else if nums[mid] > nums[low] { // in the part 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 part 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 -1
}