改图网站,企业网站推广的线上渠道有哪些,2345网址导航怎么卸载,密云建站推广这是索引二分的第二篇算法#xff0c;力扣链接
这道题其实在另一个专栏写过#xff0c;借此机会复习一下吧。 给你一个按照非递减顺序排列的整数数组 nums#xff0c;和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。 如果数组中不存在目标值 targe…这是索引二分的第二篇算法力扣链接
这道题其实在另一个专栏写过借此机会复习一下吧。 给你一个按照非递减顺序排列的整数数组 nums和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。 如果数组中不存在目标值 target返回 [-1, -1]。 你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。 示例 1 输入nums [5,7,7,8,8,10], target 8
输出[3,4] 示例 2 输入nums [5,7,7,8,8,10], target 6
输出[-1,-1] 示例 3 输入nums [], target 0
输出[-1,-1] 暴力求解
遇事不决暴力题解先来暴力求解这道题无非是在一段有序数组内找到目标值所存在的区间。
func searchRange(nums []int, target int) []int {l, r : -1, -1for i, num : range nums {if num target {break}if num target {if l -1 {l ir i} else {r i}}}return []int{l, r}
}二分查找
但题目的复杂度是log n不难想到是用二分法操作。
公式知识
说到二分法不得不借机延伸的几种解法了。
二分法的初衷是在缩小的范围内从中间开始寻找目标值。对于这个缩小的范围又会有左闭右闭、左闭右开、左开右闭的区别。这几种做法没什么本质区别熟练运用一个就行。
我最常用的二分法是左闭右闭的求解法
func search(nums []int, target int) int {l, r : 0, len(nums)-1for l r {mid : l (r-l)/2if nums[mid] target {l mid 1} else {r mid - 1}}if l len(nums) || nums[l] ! target {return -1}return l // 或者 r 1
}
左闭右开解题思路
func search(nums []int, target int) int {l, r : 0, len(nums)for l r {mid : l (r-l)/2if nums[mid] target {l mid 1} else {r mid}}if l len(nums) || nums[l] ! target {return -1}return l // 或者 r
}
左开右开解题思路
func search(nums []int, target int) int {l, r : -1, len(nums)for l1 r {mid : l (r-l)/2if nums[mid] target {l mid} else {r mid}}if l1 len(nums) || nums[l1] ! target {return -1}return l1
}
题解该题
关于这道题的第一个思路就是利用二分法找到一个值上述的三种方法都是取的靠左的值向右遍历求解即可
func searchRange(nums []int, target int) []int {l, r : 0, len(nums)-1for l r {mid : l (r-l)/2if nums[mid] target {l mid 1} else {r mid - 1}}if l len(nums) || nums[l] ! target {return []int{-1, -1}}r lfor i : l 1; i len(nums); i {if nums[i] target {r i} else {break}}return []int{l, r}
}
第二个方法是找target1找到的值作为右边界 func searchRange(nums []int, target int) []int {l : search(nums, target)if l len(nums) || nums[l] ! target {return []int{-1, -1}}r : search(nums, target1) - 1return []int{l, r}
}func search(nums []int, target int) int {l, r : 0, len(nums)-1for l r {mid : l (r-l)/2if nums[mid] target {l mid 1} else {r mid - 1}}return l
}
第三个方法就很神奇了 左右边界不赋值mid而是做/--的操作
func searchRange(nums []int, target int) []int {left, right : 0, len(nums)-1for left right {if nums[left] target nums[right] target {return []int{left, right}}if nums[left] ! target {left}if nums[right] ! target {right--}}return []int{-1, -1}
}
