🎧 fe tutorial

Appearance

Return to top
On this page

二分查找的变形

前面是最简单的一种情况，在不存在重复元素的有序数组中，查找等于给定值的元素。二分查找的变形问题很多，看看几个经典的。

查找第一个等于给定值的元素

如果有序的数据集合存在重复元素，怎么找到第一个等于给定值的元素呢？

js
function binarySearchFirst(arr, target) {
  if (arr.length === 0) return -1;
  let low = 0;
  let high = arr.length - 1;
  while (low <= high) {
    let mid = Math.floor((low + high) / 2);
    if (arr[mid] < target) {
      low = mid + 1;
    } else if (arr[mid] > target) {
      high = mid - 1;
    } else {
      // 如果 mid 等于 0，说明这个元素已经是第一个了；
      // 如果 mid 不等于 0，但是 arr[mid] 的前一个元素小于 target，
      // 那也说明 arr[mid] 就是第一个等于给定值的元素。
      if (mid === 0 || arr[mid - 1] < target) {
        return mid;
      } else {
        high = mid - 1;
      }
    }
  }
  return -1;
}
var arr = [1, 2, 3, 4, 5, 5, 7, 7, 7, 8, 8, 9];
binarySearchFirst(arr, 7);

查找最后一个等于给定值的元素

上面是查找第一个，现在查找最后一个，只需要稍微改一下判断。

js
function binarySearchLast(arr, target) {
  if (arr.length === 0) return -1;
  let low = 0;
  let high = arr.length - 1;
  while (low <= high) {
    let mid = Math.floor((low + high) / 2);
    if (arr[mid] < target) {
      low = mid + 1;
    } else if (arr[mid] > target) {
      high = mid - 1;
    } else {
      // 如果 mid 等于 arr.length - 1，说明这个元素已经是最后一个了；
      // 如果 mid 不等于 arr.length - 1，但是 arr[mid] 的后一个元素大于 target，
      // 那也说明 arr[mid] 就是最后一个等于给定值的元素。
      if (mid === arr.length - 1 || arr[mid + 1] > target) {
        return mid;
      } else {
        low = mid + 1;
      }
    }
  }
  return -1;
}
var arr = [1, 2, 3, 4, 5, 5, 7, 7, 7, 8, 8, 9];
binarySearchLast(arr, 7);

查找第一个大于等于给定值的元素

实现思路类型，甚至代码更简洁。

js
function binarySearchFirstBig(arr, target) {
  if (arr.length === 0) return -1;
  let low = 0;
  let high = arr.length - 1;
  while (low <= high) {
    let mid = Math.floor((low + high) / 2);
    if (arr[mid] >= target) {
      if (mid === 0 || arr[mid - 1] < target) {
        return mid;
      } else {
        high = mid - 1;
      }
    } else {
      low = mid + 1;
    }
  }
  return -1;
}
var arr = [1, 2, 3, 4, 5, 5, 7, 7, 7, 8, 8, 9];
binarySearchFirstBig(arr, 5);

查找最后一个小于等于给定值的元素

js
function binarySearchLastSmall(arr, target) {
  if (arr.length === 0) return -1;
  let low = 0;
  let high = arr.length - 1;
  while (low <= high) {
    let mid = Math.floor((low + high) / 2);
    if (arr[mid] > target) {
      high = mid - 1;
    } else {
      if (mid === arr.length - 1 || arr[mid + 1] > target) {
        return mid;
      } else {
        low = mid + 1;
      }
    }
  }
  return -1;
}
var arr = [1, 2, 3, 4, 5, 5, 7, 7, 7, 8, 8, 9];
binarySearchLastSmall(arr, 5);

写二分查住的时候，注意终止条件、区间上下界更新方法、返回值选择。

Edit this page on GitHub