81.M 搜索旋转排序数组 II

Problem: 81. 搜索旋转排序数组 II

思路

与题目搜索旋转排序数组相比，需要增加对于nums[mid]刚好同时等于nums[left]和nums[right]时的处理，此时只能让左右边界分别往中间收缩一个位置，其他的逻辑都是一样的

Code

func search(nums []int, target int) bool {
	left, right := 0, len(nums)-1
	for left <= right {
		mid := left + (right-left)/2
		if nums[mid] == target {
			return true
		}

		if nums[left] == nums[mid] && nums[mid] == nums[right] {
			//无法判断哪一段是有序的
			left++
			right--
		} else if nums[left] <= nums[mid] {
			if nums[left] <= target && target < nums[mid] {
				right = mid - 1
			} else {
				left = mid + 1
			}
		} else {
			if nums[mid] < target && target <= nums[right] {
				left = mid + 1
			} else {
				right = mid - 1
			}
		}
	}

	return false
}