当前位置: 首页 > news >正文

爱藏网一家专业做收藏品的网站免费发布广告信息平台

爱藏网一家专业做收藏品的网站,免费发布广告信息平台,WordPress logo生成,上海 专业网站设计今日题目: 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 所呈现出来的结果的性质

在这里插入图片描述

  1. high 最后一定是在 low 左边,而且 high == low - 1,形成一个交错
  2. 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 自然就成了右边界。

所以寻找右边界的二分写法是:

在这里插入图片描述
注意这里与找左边界的区别。

http://www.hengruixuexiao.com/news/23878.html

相关文章:

  • 网站建设销售怎么样优化排名seo
  • wordpress主题图片百度推广关键词怎么优化
  • 绍兴网站建设郑州网站seo优化
  • 企业网站建设的核心全球十大搜索引擎排名及网址
  • 怎么做网站demo百度推广引流
  • 做网站公司哪个好营销软件培训
  • wordpress 加速插件宁波网站seo公司
  • 做网站开发需要学什么软件绍兴seo公司
  • 携程电子商务网站建设上海网络推广营销策划方案
  • 响应式模板网站建设网站流量查询网站统计查询
  • 如何建设网站的管理平台做网站推广一般多少钱
  • 工信部备案网站查询宁波网站建设公司
  • 驰业网站建设中国教育培训网
  • wordpress新建网站seo企业站收录
  • 类似开发次元世界seo是什么意思电商
  • 站酷设计网站首页win10优化大师怎么样
  • 主流网站类型广告公司联系方式
  • 做消费信贷网站价格网上推销产品的软件
  • 宣城网站优化网页设计友情链接怎么做
  • 比较好的做外贸网站seo排名工具
  • 网站开发业务需求分析列举五种网络营销模式
  • 长沙的互联网公司广西seo关键词怎么优化
  • 重庆网站建设微信seo
  • 丹江口网站建设谷歌seo优化技巧
  • 株洲定制网站建设网络营销首先要做什么
  • 网站建设方案设计谷歌浏览器官网下载安装
  • 北京国贸网站建设营销型网站定制
  • 网站续费能自己续费吗网站关键词排名怎么优化
  • 哪个网站生鲜配送做的好处沈阳专业seo关键词优化
  • b站免费版2023最新版本杭州谷歌推广