34-在排序数组中查找元素的第一个和最后一个位置

题目描述

原题链接

给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。

如果数组中不存在目标值 target，返回 [-1, -1]。

// @lc code=start
func searchRange(nums []int, target int) []int {
	left, right := 0, len(nums)-1

	for left <= right {
		mid := (right-left)/2 + left

		if nums[mid] == target {
			// 找到了，再往左右找
			l, r := mid, mid
			for l >= 0 && nums[l] == target {
				l--
			}
			for r < len(nums) && nums[r] == target {
				r++
			}
			return []int{l + 1, r - 1}
		}

		// 没找到，继续二分
		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 []int{-1, -1}
}