LeetCode0034.在排序数组中查找元素的第一个和最后一个位置 Go语言AC笔记

时间复杂度：O(log n)

题目要求时间复杂度为O(log n)且数组有序，那就必须想到二分查找。

第一遍二分查找找的是第一个target位置，第二遍二分查找找的是最后一个target位置。

至于如何找到第一个target位置其实很简单，只需要根据普通的二分查找稍加修改即可，修改的位置便是target==nums[mid]时。对于一般的二分查找，既然target==nums[mid]，我们就可以立即返回mid，但是现在我们的目标是找到第一个target，所以我们不可以直接返回mid而是要加上相应的判断。仔细想想，什么时候nums[mid]就是我们要找的第一个target呢？第一种情况是nums[mid-1]与target不相等，此时nums[mid]一定是打头的第一个target。那如果mid==0呢？此时nums[mid]也肯定是第一个target呀，这就是第二种情况！所以综上所述，只有这两种情况我们才可以返回mid，否则即使target==nums[mid]了我们也要查找[low,mid-1]的区间元素来寻找第一个target。

找到最后一个target也是同理，即使target==nums[mid]也不能轻易返回mid，而是要做判断当前nums[mid]究竟是不是最后一个target，如果不是那就要继续查找[mid+1,high]区间找到最后一个target。

func searchRange(nums []int, target int) []int {
    return []int{searchFirstEqualElement(nums,target),searchLastEqualElement(nums,target)}
}

//找第一个target
func searchFirstEqualElement(nums []int,target int) int {
    low,high:=0,len(nums)-1
    for low<=high {
        mid:=low+((high-low)>>1)
        if target>nums[mid]{
            low=mid+1
        }else if target>1)
        if target>nums[mid]{
            low=mid+1
        }else if target 
感悟 
第一次提交结果超时，经排查是mid赋值时出现了问题，一开始写的是mid:=low+high>>1，可能由于数组长度过长导致low+high溢出所以就超时了。mid赋值语句修改后就解决了这个问题。
 
二分搜索有四大基础变种题，分别是
 
查找第一个等于给定值的元素
查找最后一个等于给定值的元素
查找第一个大于等于给定值的元素
查找最后一个小于等于给定值的元素
而该题目刚好满足前两种情况。
 
后两种情况的代码如下
 
//查找第一个大于等于target 的元素
func searchFirstGreaterElement(nums []int, target int) int {
	low, high := 0, len(nums)-1
	for low <= high {
		mid := low + ((high - low) >> 1)
		if nums[mid] >= target {
			if (mid == 0) || (nums[mid-1] < target) { // 找到第一个大于等于 target 的元素
				return mid
			}
			high = mid - 1
		} else {
			low = mid + 1
		}
	}
	return -1
}

// 查找最后一个小于等于 target 的元素
func searchLastLessElement(nums []int, target int) int {
	low, high := 0, len(nums)-1
	for low <= high {
		mid := low + ((high - low) >> 1)
		if nums[mid] <= target {
			if (mid == len(nums)-1) || (nums[mid+1] > target) { // 找到最后一个小于等于 target 的元素
				return mid
			}
			low = mid + 1
		} else {
			high = mid - 1
		}
	}
	return -1
}