LeetCode 033 Search in Rotated Sorted Array

LeetCode

There is an integer array nums sorted in ascending order (with distinct values).

Prior to being passed to your function, nums is possibly rotated at an unknown pivot index k (1 <= k < nums.length) such that the resulting array is [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]] (0-indexed). For example, [0,1,2,4,5,6,7] might be rotated at pivot index 3 and become [4,5,6,7,0,1,2].

Given the array nums after the possible rotation and an integer target, return the index of target if it is in nums, or -1 if it is not in nums.

You must write an algorithm with O(log n) runtime complexity.

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

Example 3:

Input: nums = [1], target = 0
Output: -1

Constraints:

1 <= nums.length <= 5000 -10<sup>4</sup> <= nums[i] <= 10<sup>4</sup>
All values of nums are unique. nums is an ascending array that is possibly rotated.
* -10<sup>4</sup> <= target <= 10<sup>4</sup>

题目大意：

有序数组旋转了几位，求target的下标

算法思路：

N/A

注意事项：

1. 四种情况： 左半有序且target在这个有序区间内，左边有序的所有其他情况，右半有序且target在这个有序区间，右半有序的所有其他情况

Python代码：

def search(self, nums: List[int], target: int) -> int:
	start, end = 0, len(nums) - 1
	while start + 1 < end:
		mid = start + (end - start) // 2
		if nums[start] < nums[mid] and nums[start] <= target <= nums[mid]:  # remember
			end = mid
		elif nums[start] < nums[mid]:
			start = mid
		elif nums[mid] < nums[end] and nums[mid] <= target <= nums[end]:
			start = mid
		else:
			end = mid
	if nums[start] == target:
		return start
	if nums[end] == target:
		return end
	return -1

Java代码：

public int search(int[] nums, int target) {
	if(nums == null || nums.length == 0)
		return -1;
	
	int start = 0, end = nums.length - 1;
	while(start + 1 < end) {
		int mid = start + (end - start) / 2;
		if(nums[mid] > nums[start]) { // the left segment is increasing
			// pay attention to equal 
			if(nums[start] <= target && target <= nums[mid]) //the [start, mid] is increasing
				end = mid;
			else
				start = mid;
		} 
		else { 
			if(nums[mid] <= target && target <= nums[end]) // the [mid, end] is increasing
				start = mid;
			else
				end = mid;
		}
	}
	
	if(nums[start] == target)
		return start;
	if(nums[end] == target)
		return end;
	
	return -1;
}

算法分析：

时间复杂度为O(logn)，空间复杂度O(1)