二分查找-模板三

• 模板三
• 模板代码
  • 代码
  • 区分语法
• 关键点

模板三

模板三我感觉并不强大，也不常用，基本模板一和模板二覆盖99%的场景，这里只简单列出模板代码，不做过多分析。

模板代码

代码

function binarySearch_template_3(nums, target) {
  if (!nums.length) return -1;
  let left = 0;
  let right = nums.length - 1;
  while (left + 1 < right) {
    let mid = (left + right) >>> 1;
    if (nums[mid] == target) {
      return mid;
    } else if (nums[mid] < target) {
      left = mid;
    } else {
      right = mid;
    }
  }

  // Post-processing:
  // End Condition: left + 1 == right
  if (nums[left] == target) return left;
  if (nums[right] == target) return right;
  return -1;
}

区分语法

• 初始条件：left = 0, right = length-1
• 循环条件：while (left + 1 < right)
• 终止：left + 1 == right
• 向左查找：right = mid
• 向右查找：left = mid

关键点

• 实现二分查找的另一种方法。
• 搜索条件需要访问元素的直接左右邻居。
• 使用元素的邻居来确定它是向右还是向左。
• 保证查找空间在每个步骤中至少有 3 个元素。
• 需要进行后处理。 当剩下 2 个元素时，循环 / 递归结束。 需要评估其余元素是否符合条件。