二分查找的细节坑

二分查找的坑

介绍

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

问题

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

分析

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

• 首先第一个坑是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