以我所主，为我所用

算法：二分查找

5分钟阅读

定义

针对有序的数据集合，查找思想类似于分治思想。每次都通过跟区间的中间元素对比，将待查找的区间缩小为之前的一般，直到找到要查找的元素，区间被缩小为 0

基础实现

const bsearch = (array: number[], target: number) => {
  let low = 0;
  let high = array.length - 1;
 
  // 注意点1：low <= high，而不是 low < high
  while (low <= high) {
    // 注意点2：low + high 的和可能会溢出，使用下面的写法
    // const mid = Math.floor((low + high) / 2);
    const mid = low + (high - low) / 2;
    // 位运算更高效
    // const mid = low + ((high - low) >> 1);
    if (array[mid] === target) {
      return mid;
    }
 
    // 注意点3：low 和 high 的更新，不能写成 low=mid 活着 high=mid。
    // 比如 low 和 high 都等于 3 时，array[3]不等于 target，就会导致一直循环不退出
    if (array[mid] > target) {
      low = mid + 1;
    }
    if (array[mid] < target) {
      high = mid - 1;
    }
  }
  return -1;
};

局限性

  1. 二分查找依赖于数据结构：数组这个数据结构，因为需要根据下标随机访问数组。根据数组下标随机访问的时间复杂度为 O(1)，用数据结构：链表随机访问的时间复杂度为 O(n)
  2. 只能处理插入、删除操作不频繁的有序数据中，无序数据需要预先算法：排序，对于动态数据，需要借助二叉树来实现。
  3. 对于数据量太小的场景不适合使用二分查找，效率提升不高。除非元素和元素之间的比对很耗时。比如整个数组中都是长度超过 300 的字符串，为了减小字符串对比的耗时影响，我们需要尽可能地减少比对次数，此时二分查找和顺序遍历更加合适
  4. 对于数据量太大的场景不适合使用二分查找。数据结构：数组的特性是连续的内存空间，如果我们拿不到足够大小的内存空间，也就无法构造大型数据结构：数组，自然就无法使用二分查找了。

变体

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

const bsearch = (array: number[], target: number) => {
  let low = 0;
  let high = array.length - 1;
 
  while (low <= high) {
    const mid = (low + (high - low)) >> 1;
    if (array[mid] > target) {
      low = mid + 1;
    }
    if (array[mid] < target) {
      high = mid - 1;
    }
	// 如果 mid 为0，那么它肯定是我们要找的
	// 如果 mid 不为0，且上一个和当前值不一致，那这个值就是我们要找的
    if (mid === 0 || array[mid - 1] !== target) {
      return mid;
    }
    high = mid - 1;
  }
  return -1;
};

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

const bsearch = (array: number[], target: number) => {
  let low = 0;
  let high = array.length - 1;
 
  while (low <= high) {
    const mid = (low + (high - low)) >> 1;
    if (array[mid] > target) {
      low = mid + 1;
    }
    if (array[mid] < target) {
      high = mid - 1;
    }
 
    if (mid === array.length - 1 || array[mid + 1] !== target) {
      return mid;
    }
 
    low = mid + 1;
  }
  return -1;
};

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

const bsearch = (array: number[], target: number) => {
  let low = 0;
  let high = array.length - 1;
 
  while (low <= high) {
    const mid = (low + (high - low)) >> 1;
    if (array[mid] >= target) {
      if (mid === 0 || array[mid - 1] < target) {
        return mid;
      } else {
        high = mid - 1;
      }
    } else {
      low = mid + 1;
    }
  }
  return -1;
};

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

const bsearch = (array: number[], target: number) => {
  let low = 0;
  let high = array.length - 1;
 
  while (low <= high) {
    const mid = (low + (high - low)) >> 1;
    if (array[mid] >= target) {
      if (mid === 0 || array[mid - 1] < target) {
        return mid;
      } else {
        high = mid - 1;
      }
    } else {
      low = mid + 1;
    }
  }
  return -1;
};

关系图谱