左手

V1

2022/08/08阅读:15主题:默认主题

二分查找的坑

二分查找的坑

介绍

  • 二分查找是一个十分容易理解的一中算法,原理非常的简单,就是不断取出中间值进行对比,最终得出结果(这里不做过多介绍)

问题

  • 二分查找容易写错
  • 循环的判断条件有时候可以,有时候又不行
  • 中间值索引取值,left/right = mid? mid+1? mid-1?
  • 不一样的题用同样的二分查找就出现各种问题?

分析

​ 先随机打开一个力扣的简单题,看看别人的题解

image-20220725093001745
image-20220725093001745
  • 首先第一个坑是mid的溢出问题

这里不做介绍,一般都是用: (大 - 小) / 2 + 小 等价于:(大 + 小)/ 2

  • 循环条件问题

自己写的时候,有时候的循环条件没问题,有时候就这么也跳不出循环,看别人的题解的条件又是五花八门

  • 高低移位问题

高低移位也是和循环条件差不多,题解五花八门,和循环条件又紧紧相关

解决

​ 视频链接:https://www.bilibili.com/video/BV1d54y1q7k7?spm_id_from=333.337.search-card.all.click

其实二分查找还是容易被忽视的,有非常多的细节,看了大佬的讲解收获还是比较大的,至少固定了属于自己的模板,在实际刷题就没有那么多烦恼和问题

  • 循环条件

left + 1 < right

  • 移位(没有+-1的问题)

left/right = mid

  • 返回(没有返回left/right的问题)

mid

分类:

后端

标签:

后端

作者介绍

左手
V1