【算法方法总结·一】二分法的一些技巧和注意事项

  • 【算法方法总结·一】二分法的一些技巧和注意事项 🎯
  • 【算法方法总结·二】双指针的一些技巧和注意事项
  • 【算法方法总结·三】滑动窗口的一些技巧和注意事项
  • 【算法方法总结·四】字符串操作的一些技巧和注意事项
  • 【算法方法总结·五】链表操作的一些技巧和注意事项
  • 【算法方法总结·六】栈队列堆的一些技巧和注意事项

【二分法】

  • 对于有些题目 暴力解法 时间复杂度为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

相关力扣题

  • 相关解法见【算法题解答·一】二分法

34.在排序数组中查找元素第一和最后一个位置

35.搜索插入位置

74.搜索二维矩阵

33.搜索旋转排序数组

153.寻找旋转排序数组中的最小值

4.寻找两个正序数组的中位数