基本思想
- 二分查找也称折半查找（Binary Search），是一种在 有序数组中查找 某一特定元素的搜索算法；
- 可以从定义可知，运用二分搜索的前提是数组必须是有序的，这里需要注意的是，输入不一定是数组，也可以是数组中某一区间的起始位置和终止位置；
时间复杂度分析
-
由于 二分查找 每一次都将问题近似地缩减为上一次问题规模的一半，最差情况下，也就是没有找到目标元素的时候，最后两步，区间里剩下的元素个数依次为 1 和 0；
二分次数 结果范围 第一次 N 第二次 N/2 第三次 N/4 … … 倒数第三次 2 倒数第二次 1 最后一次 0 -
由于循环体内部的操作次数是常数次的，因此循环体执行的次数就是 二分查找 算法的时间复杂度；
-
根据上面表格可知二分查找是一个 等比数列 即
2^x = n=>x = log2^n，时间复杂度为logn；
二分搜索分类
左闭右闭的二分
-
定义 target 是在一个在 左闭右闭 的区间里，也就是 [left, right]；区间的定义决定了二分法的代码应该如何写，因为定义 target 在 [left, right] 区间，所以有如下两点：
while(left <= right)，因为 left == right 在 [left, right] 区间是有意义的，所以使用 <=；if(nums[middle] > target)，因为当前这个 nums[middle] 一定不是 target ，那么接下来要查找的左区间结束下标位置就是 right = middle - 1；
-
图解
![]( "左闭右闭")
-
实现代码
const search = (nums: number[], target: number): number => { let left = 0; let right = nums.length - 1; while (left <= right) { // 当 left==right 在区间 [left, right] 依然有效，所以用 <= const middle = (left + right) >>> 1; if (nums[middle] > target) { right = middle - 1; } else if (nums[middle] < target) { left = middle + 1; } else { return middle; } } return -1; // 未找到目标值 }
左闭右开的二分
-
定义 target 是在一个在 左闭右开 的区间里，也就是 [left, right)；那么二分法的边界处理方式则截然不同，有如下两点：
while(left < right)，因为 left == right 在区间 [left, right) 是没有意义的，所以使用 <；if(nums[middle] > target)，因为当前 nums[middle] 不等于 target ，去左区间继续寻找，而寻找区间是左闭右开区间，所以 right = middle ，即：下一个查询区间不会去比较 nums[middle]；
-
图解
![]( "左闭右开")
-
实现代码
const search = (nums: number[], target: number): number => { let left = 0; let right = nums.length; while (left < right) { // 当 left==right 在区间 [left, right] 依然有效，所以用 < const middle = (left + right) >>> 1; if (nums[middle] > target) { right = middle; } else if (nums[middle] < target) { left = middle + 1; } else { return middle; } } return -1; // 未找到目标值 }
mid 值的计算
-
在 left 和 right 很大的时候，left + right 有可能会发生整型溢出，推荐写成：
// 第一种 let mid = left + Math.floor((right - left) / 2); // 第二种：>>> 是无符号右移，在 left + right 发生整型溢出的时候，右移一位由于高位补 0 ，依然能够保证结果正确 let mid = (left + right) >>> 1; // 第三种： let mid = left + ((right - left) >> 1); -
mid 向下取整时，条件体中的
left = mid可能出现死循环，需要注意；
应用案例
leftpad 可以在字符串前面添加指定数量的填充字符
leftpad(str, length [, ch])
-
原 leftpad 没有利用二分思想，暴力迭代被广为吐槽；
function leftpad(str, length, ch) { let len = length - str.length + 1; return Array(len).join(ch) + str; } -
优化后的 leftpad 利用了二分思想
function leftpad2(str, length, ch) { let len = length - str.length; total = ''; while (true) { if (len & 1) total += ch; // (len%2 == 1) 等价 (len & 1) if (len == 1) return total + str; // 每次循环，len除以2，len变成了原来的一半，那么循环次数相应减少到原来的一半，那么ch相应应该增加到原来的两倍的长度ch=ch+ch // 这样每次循环都将len减少到原来的一半,这样就将原本O(n)的复杂度减少到了O(log(n)) ch += ch; len = len >> 1; // len = parseInt(len/2) } } -
leftpad 优化前后的性能对比
console.time('leftpad 优化前') for (let i = 0; i < 10000; i++) { leftpad('hello', 1000, '0') } console.timeEnd('leftpad 优化前') // 66ms console.time('leftpad 优化后') for (let i = 0; i < 10000; i++) { leftpad2('hello', 1000, '0') } console.timeEnd('leftpad 优化后') // 11ms
参考资料
打赏作者
您的打赏是我前进的动力
微信
支付宝
算法基础🔮 优先级队列
上一篇
评论
