关于r的位置

关于r的位置

https://img1.sycdn.imooc.com//climg/62f4a316092d388f25601600.jpg

老师,这里反复听了几遍,我还是没有理解为啥子r要多一个位置出来

正在回答 回答被采纳积分+1

登陆购买课程后可参与讨论,去登陆

2回答
坐着谷堆望着天 2024-05-30 09:24:59
大致的思路是  找比 target 大的数,那么就不要把 这个数的范围 局限在数组内部。
因为 target有可能是数组最后一个值(那么 比target大的最小值 数组中就找不到) target有可能比数组最后一个值还大(比target大的最小值 数组中就找不到)
既然数组中的这些数有可能是找不到,那么就把查找的范围定义的更广泛一些,扩大右边界就行,把右边界设置为arr.length,数组最后一个值的下一位。
这样当返回结果是右边界 arr.length,那么就是以上两种情况之一。属于预先处理了一些细节,方便后续的操作。


  • 大致的思路是  找比 target 大的数,那么就不要把 这个数的范围 局限在数组内部。
    因为 target有可能是数组最后一个值(那么 比target大的最小值 数组中就找不到) target有可能比数组最后一个值还大(比target大的最小值 数组中就找不到)
    既然数组中的这些数有可能是找不到,那么就把查找的范围定义的更广泛一些,扩大右边界就行,把右边界设置为arr.length,数组最后一个值的下一位。
    这样当返回结果是右边界 arr.length,那么就是以上两种情况之一。属于预先处理了一些细节,方便后续的操作。

    2024-05-30 09:26:16
liuyubobobo 2022-08-11 14:47:18

比如对于截图中的数据。如果要找大于 100 的最小值怎么办?


整个数组没有任何数值大于 100,更谈不上大于 100 的最小值。整个数组的最大值都比 100 小。此时,我们的算法将返回 arr.length。(即超过了整个数组的索引范围。)


继续加油!:)

  • 提问者 Star3327752 #1

    如果要找大于 100 的最小值怎么办?

    对于没有找到的数值,直接返回-1不就可以了吗?为啥要返回arr.length嘞

    2022-08-11 15:17:57
  • liuyubobobo 回复 提问者 Star3327752 #2

    你可以定义成返回 -1。但我建议你先跟着我的逻辑走,理解我在课程中的算法的执行思路(然后你就会发现,返回 arr.length 特别自然),然后思考一下,如果我想要在这种情况下返回 -1,逻辑要怎么写?


    另外,你会发现,我在课程中的代码,如果要找小于某个值的最大值,找不到的情况下返回就是 -1 了。思考一下,这是为什么?我为什么将这两个算法同样是“找不到”,定义的返回值不同?


    (依然是,你可以用你自己的方式定义,你可以编写属于自己的逻辑。但是上面我提出的这些问题值得思考。对你更深入理解二分搜索是有意义的。)



    2022-08-11 15:20:09
问题已解决,确定采纳
还有疑问,暂不采纳

恭喜解决一个难题,获得1积分~

来为老师/同学的回答评分吧

0 星
算法与数据结构
  • 参与学习       2589    人
  • 解答问题       1090    个

慕课网算法名师Liuyubobobo,5年集大成之作 从0到工作5年,算法与数据结构系统解决方案

了解课程
请稍等 ...
意见反馈 帮助中心 APP下载
官方微信

在线咨询

领取优惠

免费试听

领取大纲

扫描二维码,添加
你的专属老师