【Go语言LeetCode刷题手记|第四天】34. 在排序数组中查找元素的第一个和最后一个位置 35. 搜索插入位置

目录

前言

34. 在排序数组中查找元素的第一个和最后一个位置 - 力扣（LeetCode）

35. 搜索插入位置 - 力扣（LeetCode）

前言

今天我们来刷两道二分查找的题目。

34. 在排序数组中查找元素的第一个和最后一个位置 - 力扣（LeetCode）

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

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

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

这道题目是如果用暴力做法，一个一个遍历数组找到第一个大于等于target的，并且找到最后一个小于等于target的，最坏的情况是target在数组末尾，也就是需要O(n)的时间复杂度，那我们如何才能做到O(log n)的时间复杂度呢？就需要用到我们的二分查找，设置两个指针，一个指向数组开头，一个指向数组末尾，每次取数组最中间的值mid，如果mid指向的值小于target，那么mid左边一定也小于target，反之亦然，这样我们每一次就可以得到数组中一半的元素与target的关系，也就可以将时间复杂度降低到O(log n)。具体见代码：

func searchRange(nums []int, target int) []int { start := lowerBound(nums, target) //找到第一个大于等于target的值 if start == len(nums) || nums[start] != target{ // 如果不存在，直接返回[-1,-1] return []int{-1, -1} } end := lowerBound(nums, target+1) - 1 // 找到第一个大于等于target+1的值，前一个位置就是最后一个小于等于target的位置 return []int{start, end} //返回 } func lowerBound(nums []int, target int) int { // 二分查找模板 left := 0 right := len(nums) - 1 for left <= right { mid := left + (right-left)/2 //防止溢出 if nums[mid] < target { left = mid + 1 }else { right = mid - 1 } } return left }

注意：这里的lowerBound(nums, target)，相信大家都可以理解，但是如何理解lowerBound(nums, target+1) - 1这行代码？这就需要用到一个小技巧，这样我们用下面这套模板就可以解决四种情况的问题（第一个>target,第一个>=target,最后一个<target,最后一个<=target）。

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

第一个>=target的值我们可以直接用lowerBound(nums, target)，第一个>target的值我们可以转化为第一个>=target+1，最后一个<=target可以转化为第一个>target的值的前一个位置，最后一个＜target可以转化为第一个>=target的值的前一个位置，如下表：

这样我们只用一套模板就可以解决全部二分查找的问题。

35. 搜索插入位置 - 力扣（LeetCode）

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

请必须使用时间复杂度为O(log n)的算法。

这道题目也是有一个标准的二分查找模板题，相信搞懂了上一题，这道题目也不在话下，直接秒杀，代码：

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