二分查找及变种

问题

实现二分查找的基本形式，以及以下变种：

• 查找第一个等于目标值的位置
• 查找最后一个等于目标值的位置
• 查找第一个大于等于目标值的位置
• 查找最后一个小于等于目标值的位置

解答

基本二分查找

// 在有序数组中查找目标值，返回索引，不存在返回 -1
function binarySearch(nums, target) {
  let left = 0;
  let right = nums.length - 1;

  while (left <= right) {
    // 防止溢出的写法
    const mid = left + Math.floor((right - left) / 2);

    if (nums[mid] === target) {
      return mid;
    } else if (nums[mid] < target) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }

  return -1;
}

// 测试
console.log(binarySearch([1, 2, 3, 4, 5], 3)); // 2
console.log(binarySearch([1, 2, 3, 4, 5], 6)); // -1

查找第一个等于目标值的位置

function findFirst(nums, target) {
  let left = 0;
  let right = nums.length - 1;
  let result = -1;

  while (left <= right) {
    const mid = left + Math.floor((right - left) / 2);

    if (nums[mid] === target) {
      result = mid;
      // 找到后继续向左搜索
      right = mid - 1;
    } else if (nums[mid] < target) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }

  return result;
}

// 测试
console.log(findFirst([1, 2, 2, 2, 3], 2)); // 1

查找最后一个等于目标值的位置

function findLast(nums, target) {
  let left = 0;
  let right = nums.length - 1;
  let result = -1;

  while (left <= right) {
    const mid = left + Math.floor((right - left) / 2);

    if (nums[mid] === target) {
      result = mid;
      // 找到后继续向右搜索
      left = mid + 1;
    } else if (nums[mid] < target) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }

  return result;
}

// 测试
console.log(findLast([1, 2, 2, 2, 3], 2)); // 3

查找第一个大于等于目标值的位置（lower_bound）

function lowerBound(nums, target) {
  let left = 0;
  let right = nums.length;

  while (left < right) {
    const mid = left + Math.floor((right - left) / 2);

    if (nums[mid] < target) {
      left = mid + 1;
    } else {
      // nums[mid] >= target，可能是答案，收缩右边界
      right = mid;
    }
  }

  return left;
}

// 测试
console.log(lowerBound([1, 2, 4, 5], 3)); // 2（第一个 >= 3 的是 4）
console.log(lowerBound([1, 2, 4, 5], 2)); // 1

查找最后一个小于等于目标值的位置

function lastLessOrEqual(nums, target) {
  let left = 0;
  let right = nums.length;

  while (left < right) {
    const mid = left + Math.floor((right - left) / 2);

    if (nums[mid] <= target) {
      // nums[mid] <= target，可能是答案，收缩左边界
      left = mid + 1;
    } else {
      right = mid;
    }
  }

  // left - 1 是最后一个 <= target 的位置
  return left - 1;
}

// 测试
console.log(lastLessOrEqual([1, 2, 4, 5], 3)); // 1（最后一个 <= 3 的是 2）
console.log(lastLessOrEqual([1, 2, 4, 5], 4)); // 2

统一模板

// 红蓝染色法：将数组分成两部分，找分界点
function binarySearchTemplate(nums, condition) {
  let left = -1;        // 红色区域右边界
  let right = nums.length; // 蓝色区域左边界

  while (left + 1 < right) {
    const mid = left + Math.floor((right - left) / 2);

    if (condition(nums[mid])) {
      right = mid; // mid 满足条件，属于蓝色
    } else {
      left = mid;  // mid 不满足条件，属于红色
    }
  }

  // right 是第一个满足条件的位置
  // left 是最后一个不满足条件的位置
  return right;
}

// 使用示例：查找第一个 >= 3 的位置
const nums = [1, 2, 4, 5];
const result = binarySearchTemplate(nums, (x) => x >= 3);
console.log(result); // 2

关键点

• left <= right 用于查找具体值，left < right 用于查找边界
• mid = left + (right - left) / 2 防止整数溢出
• 找第一个：找到后收缩右边界（right = mid 或 right = mid - 1）
• 找最后一个：找到后收缩左边界（left = mid + 1）
• 注意边界初始值和返回值的处理，避免越界