建设网站必备条件,网站名称可以是域名,免费制作头像,wordpress 在线敏感词今日题目#xff1a; 704. 二分查找35. 搜索插入位置34. 在排序数组中查找元素的第一个和最后一个位置 目录 今日总结Problem 1: 二分法LeetCode 704. 二分查找 【easy】LeetCode 35. 搜索插入位置 ⭐⭐⭐⭐⭐LeetCode 34. 在排序数组中查找元素的第一个和最后一个位置 【medi… 今日题目 704. 二分查找35. 搜索插入位置34. 在排序数组中查找元素的第一个和最后一个位置 目录 今日总结Problem 1: 二分法LeetCode 704. 二分查找 【easy】LeetCode 35. 搜索插入位置 ⭐⭐⭐⭐⭐LeetCode 34. 在排序数组中查找元素的第一个和最后一个位置 【medium】 今日总结
重点学习了使用二分法来解决问题需要特别理解的是二分法在通过 while(low high) 循环后low 与 high 的关系所呈现出来的性质以及为什么能够呈现这样的性质。利用这个性质可以更容易地解决相关问题。
Problem 1: 二分法
LeetCode 704. 二分查找 【easy】 704. 二分查找 | LeetCode 这个题目很经典题目本身很简单但这里有一种具有普适性的写法可以用来解决其他二分查找相关的题目这里需要着重学习一下 关键理解好二分法在经过 while(low high) 这个循环后low 和 high 所呈现出来的结果的性质 high 最后一定是在 low 左边而且 high low - 1形成一个交错low 和 high 中间将数字序列划分成了两个部分 左半边从开始到 high 为止都是小于 target右半边从 low 到结束都是大于等于 target 为什么会具备这样的性质 简单来说因为 while 的判断是 low high所以最终 low 一定是大于 high。 同时low 和 high 每次更新都是基于 mid 来向前或向后一步走而 mid 是一定出现在 [low,high] 这个区间内所以每次更新的结果是low 或 high 一定是处于原先 [low,high] 范围内或者这个范围的左边或右边一个为止。所以最终一定是 high low - 1。 当然目前也很容易理解 [0, high] 一定是小于 target[low, end) 一定是大于等于 target。因为当 nums[mid] target 时我们是将 high 移动到 mid 左边这样的结果就是让等于 target 元素的值出现在了 high 右边所有右半边才会有等于 target 的元素。 在上面的代码中low 最终指向的是第一个大于等于 target 的元素但由于 target 可能不存在所以在作为结果返回时需要判断一下 low 是否在 nums 的合法范围内以及 low 指向的值是否等于 target。
学会了这个题目下面几个题目就是可以利用这里总结的性质来解决。
LeetCode 35. 搜索插入位置 ⭐⭐⭐⭐⭐ 35. 搜索插入位置 | LeetCode 通过这个题对二分法的思路有了更深入的理解。
这个题目是返回搜索的位置或者插入的位置自然也就是 low 的位置所以代码如下 整体与第一个二分法的题目一样只是最后直接把 low 给 return 出去而已。
所以学习二分法需要注意
代码中 while 的条件、low 与 high 变更的方式经过 while 循环后 low 与 high 所呈现出来的性质
LeetCode 34. 在排序数组中查找元素的第一个和最后一个位置 【medium】 34. 在排序数组中查找元素的第一个和最后一个位置 | LeetCode 这个题目就有难度了解决这个题目需要依靠我们在上面的题目中总结出来的经验。
由于题目要求复杂度 O ( log n ) O(\log n) O(logn)所以需要通过两次二分查找来分别找到左边界和右边界。
刚刚我们总结到当经过 while 循环后low 指向了第一个大于等于 target 的元素这不就是这个题目的左边界嘛所以我们可以写出找左边界的代码但是因为这个题目中 nums 中的数字是可能重复的所以我们需要做一些更改 这个代码有两点需要我们特别关注
当 val target 的时候我们是更新 low 还是 high左边界和 low 的关系
在上面代码中如果 val target那么就让 high 移动到 mid 左边这样的结果就是当 while 循环完之后等于 target 的元素都出现在了右半边也就是 [low, end) 这个区间内所以 low 才成了左边界。
同时因为 low 可能超出 nums 的索引范围以及可能没有找到 target所以给左边界 first 赋值时需要检查一下检查不通过就是赋值 -1代表没有找到。
根据刚刚的思路当 val target 时如果我们让 low 移动到 mid 右边那么 while 循环完的结果就变成了 “target 的元素都出现了左半边”也就是 [0, high] 这个区间所以 high 自然就成了右边界。
所以寻找右边界的二分写法是 注意这里与找左边界的区别。
