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

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

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

你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。

问题链接：34.在排序数组中查找元素的第一个和最后一个位置

题解

根据题目的提示O(log n)的查找算法，明显是让我们去实现一个二分查找算法实现该功能。

我们考虑在二分法中提到的两个问题，对于二分查找原始算法：

  1. left <= right 中的=是否需要，显然该问题与我们的当前问题关联性并不大
  2. 对于nums[middle]的判断条件如何设置。

考虑本题目中的第一个问题，查找元素的第一个位置。考虑如下三种情况：

  1. nums[middle] == target，此时有两种情况：
    1. middle就是target的第一个位置
    2. middle不是target的第一个位置，第一个位置应该在middle之前
  2. nums[middle] < target：target的第一个位置在middle之后
  3. nums[middle] > target: target的第一个位置在middle之前

很显然，第2，3种情况很容易处理，第1.2情况要怎么处理呢？在二分法中提到了二分法要考虑的第二个问题，即如果查找到了元素left、right指针到底在哪儿的问题？

以本题为例，当遍历到[i,i]范围内，发现:

  1. nums[i] < target时：下一步left ++，即left=i + 1，此时left指向的是大于target的第一个值，right指向小于target的第一个值
  2. nums[i] > target时：下一步right –，即right=i - 1，此时right指向的是小于target的第一个值，left指向大于target的第一个值

可以发现，对于原始的二分法，如果查找不到target，left指向大于target的第一个值，right指向小于target的第一个值。

我们可以利用这一点处理该问题的1.2的情况，如果采用这种条件：

  1. nums[middle] == target，此时有两种情况：right = middle - 1
    1. middle就是target的第一个位置
    2. middle不是target的第一个位置，第一个位置应该在middle之前
  2. nums[middle] < target：target的第一个位置在middle之后：left = middle + 1
  3. nums[middle] > target: target的第一个位置在middle之前：right = middle - 1

分析一下运行结果，当nums[middle]==target时，二分查找会一直向前查找，直到找到第一个小于target的值，因此，利用我们得到的原始二分法的特点，如果查找不到target，left指向大于target的第一个值，right指向小于target的第一个值，则此时left指针指向的位置就是我们想要的结果。

此时需要额外判断一下nums[left]与target是否相等，如果不等证明target在nums中并不存在，要返回-1。

对于查找元素的最后一个位置，与上述算法同理，这里就不过多赘述。

代码实现

func searchRange(nums []int, target int) []int {
	if len(nums) == 0 {
		return []int{-1, -1}
	}
	result := []int{}
	// 查找元素的第一个位置
	l, r := 0, len(nums)-1
	for l <= r {
		m := (l + r) / 2
		if nums[m] >= target {
			r = m - 1
		} else {
			l = m + 1
		}
	}
	if l >= len(nums) || nums[l] != target {
		result = append(result, -1)
	} else {
		result = append(result, l)
	}

	// 查找元素的最后一个位置
	l, r = 0, len(nums)-1
	for l <= r {
		m := (l + r) / 2
		if nums[m] <= target {
			l = m + 1
		} else {
			r = m - 1
		}
	}
	if r < 0 || nums[r] != target {
		result = append(result, -1)
	} else {
		result = append(result, r)
	}
	return result
}