【算法方法总结·一】二分法的一些技巧和注意事项
【算法方法总结·一】二分法的一些技巧和注意事项
- 打算归纳出一个算法章节出来，当作自己的总结回顾，敬请期待
【二分法】
- 对于有些题目 暴力解法 时间复杂度为
O(n) - 而 二分查找 的时间复杂度为
O(logn) - 这便是 二分法 的 优势 所在
两种写法
左闭右闭 [left,right]
- 其中
left == right是 有意义 的，所以while(left <= right) - 更新时，
left更新为mid + 1，right更新为mid - 1 - 所以 初始化 时，一般为
left = 0，right = n - 1
左闭右开 [left,right)
- 其中
left == right是 没有意义 的，所以while(left < right) - 更新时，
left更新为mid + 1，right更新为mid - 所以 初始化 时，一般为
left = 0，right = n
相关力扣题
- 相关解法见【算法题解答·一】二分法