33. Search in Rotated Sorted Array

	class Solution(object):
	def search(self, nums, target):
	"""
	:type nums: List[int]
	:type target: int
	:rtype: int
	"""
	# corner case: input is None or empty list
	if not nums:
	return -1

	# binary search
	left = 0
	right = len(nums) - 1
	while left <= right:
	mid = left + (right - left) // 2

	if nums[mid] == target:
	return mid

	# sorted from left to mid
	if nums[left] <= nums[mid]:
	# target in left and mid
	if target < nums[mid] and target >= nums[left]:
	right = mid - 1
	else:
	left = mid + 1

	# sorted from mid to right
	if nums[mid] <= nums[right]:
	if target > nums[mid] and target <= nums[right]:
	left = mid + 1
	else:
	right = mid - 1

	return -1

view raw 33_1017.py hosted with ❤ by GitHub

341. Flatten Nested List Iterator