TS数据结构与算法之二分查找

什么是二分查找

有序数据集合对于查找算法是很有利的。在有序集合中顺序查找时，当与第一个项进行比较，如果第一项不是要查找的，则还有 n-1 项待比较。当遇到超过范围的值时，可以停止查找，综合来看这种有序查找速度还是比较慢。对于排好序的数据集有没有更快的查找算法呢？当然有，那就是二分查找。

其实二分查找的意思体现在其名字上了，说白了就是把数据集分成两部分来查找，通过start，mid，end 来控制查找的范围。从中间项 mid 开始，而不是按顺序查找。如果中间项是正在寻找的项，则完成了查找。如果它不是，可以使用排序集合的有序性质来消除一半剩余项。如果正在查找的项大于中间项，就可以消除中间项以及比中间项小的一半元素，也就是第一项到中间项都可以不用去比较了。因为目标项大于中间值，那么不管是否在集合中，那肯定不会在前一半。相反，若是目标项小于中间项，则后面的一半数据就都可以不用比较了。去除了一半数据后在剩下的一半数据项里再查看其中间项，重复上述的比较和省略过程，最终得到结果。这个查找速度是比较快的，而且也非常形象，所以叫二分查找。

实现原理及代码

    19  20  26   33   44   56   58   66  72  92
    |                 |                      |
  start              mid                    end

二分查找示意图如上图。初始时 start 和 end 分居最左和最右。比如你要查60，那么先和中间值比较，大于44，则 start 移动到56 处，mid 移动到66。此时和 66 比较，发现小于66，所以 end 移动到58，mid 移动到56 和 start 重合了。比较发现大于56，所以 start 移动到58，mid 也移动到58，发现大于58。此时 start, end, mid 三者在一个位置。接着 start 移动到66，发现下标大于end 了，不满足条件，查找停止，退出。

循环方式

根据上面的描述和示意图，可以写出如下的二分查找代码。

/**
 * 使用循环的方式实现二分查找
 * 
 * 10  20  30 40 50 60 70
 * start      min      end
 * 
 * @param arr 要查找的数组
 * @param target 目标数据
 * @return number 目标数据索引下标
 */
export const binarySearch1 = (arr: number[], target: number): number => {
  const len = arr.length;
  if (!len) return -1;

  // 起始索引
  let startIndex = 0;
  // 结束索引
  let endIndex = len - 1;
  
  while (startIndex <= endIndex) {
    let midIndex = Math.floor((startIndex + endIndex) / 2);
    let midTarget = arr[midIndex];

    if (target < midTarget) {
      // 目标小于中值 舍弃右半部分
      endIndex = midIndex - 1;
    } else if (target > midTarget) {
       // 大于中值 舍弃左半部分
       startIndex = midIndex + 1;
    } else if (target === midTarget) {
      // 相同找到目标直接返回下标
      return midIndex;
    }
  }
  // 循环结束没找到
  return -1;
};

递归方式

二分法其实是把大问题分解成小问题，采取的是分而治之策略。以前了解过类似这种分解大问题为小问题可以考虑用递归来解决，那二分法和递归是否有相似，二分法是否能用递归实现呢？我们发现二分查找时，找到或没找到是最终的结果，是一个基本情况。而二分法不断减小问题的尺度，不断向基本情况靠近，且二分法是在不断重复自身步骤。所以二分法满足递归三定律，所以可以用递归实现二分法，具体实现如下。

/**
 * 使用递归的方式实现二分查找
 * 
 * @param arr 要查找的数组
 * @param target 目标数据
 * @param startIndex 起始索引
 * @param endIndex 结束索引
 * @return number 目标数据索引下标
 */
export const binarySearch2 = (
  arr: number[],
  target: number,
  startIndex?: number,
  endIndex?: number
): number => {
  const len = arr.length;
  if (!len) return -1;

  // 初始化起始索引
  let start = startIndex || 0;
  let end = endIndex || len - 1;
  
  if (start > end) return -1;

  // 计算当前中值索引
  let midIndex = Math.floor((start + end) / 2);
  const midTarget = arr[midIndex];

  if (target < midTarget) {
    // 目标小于中值 舍弃右半部分
    return binarySearch2(arr, target, start, midIndex - 1);
  } else if (target > midTarget) {
    // 大于中值 舍弃左半部分
    return binarySearch2(arr, target, midIndex + 1, end);
  } else if (target === midTarget) {
    // 相同找到目标直接返回下标
    return midIndex;
  }

  return -1;
}

递归算法总是涉及栈的使用，有爆栈风险，一般来说二分查找最好用循环迭代法来解决。

功能测试

/**
 * 功能测试
 */
export const binarySearch1FunctionalTest = () => {
  const arr = [10, 20, 30, 40, 50];
  console.log(binarySearch2(arr, 20));  // 1
  console.log(binarySearch2(arr, 30));  // 2
  console.log(binarySearch2(arr, 50)); // 4
  console.log(binarySearch2(arr, 80));  // -1
  console.log(binarySearch2(arr, 0));   // -1
}

单元测试

文件： tests/binary-search.test.ts

/**
 * 二分查找单元测试
 */
import { binarySearch1, binarySearch2 } from '../src/utils';

describe('二分查找单元测试', () => {
  test('循环方式正常测试', () => {
    const arr = [10, 20, 30, 40, 50, 60];
    expect(binarySearch1(arr, 10)).toBe(0);
    expect(binarySearch1(arr, 30)).toBe(2);
    expect(binarySearch1(arr, 40)).toBe(3);
    expect(binarySearch1(arr, 80)).toBe(-1);
    expect(binarySearch1(arr, -100)).toBe(-1);
  });

  test('递归方式正常测试', () => {
    const arr = [10, 20, 30, 40, 50, 60];
    expect(binarySearch2(arr, 10)).toBe(0);
    expect(binarySearch2(arr, 30)).toBe(2);
    expect(binarySearch2(arr, 40)).toBe(3);
    expect(binarySearch2(arr, 80)).toBe(-1);
    expect(binarySearch2(arr, -100)).toBe(-1);
  });

  test('空数据', () => {
    expect(binarySearch1([], 10)).toBe(-1);
    expect(binarySearch2([], 10)).toBe(-1);
  });
});

单元测试执行结果(测试通过)：

PASS  tests/binary-search.test.ts (8.263 s)
  二分查找单元测试
    ✓ 循环方式正常测试 (3 ms)
    ✓ 递归方式正常测试
    ✓ 空数据 (1 ms)

性能测试

循环使用两种查询方式操作100W次

/**
 * 性能测试
 */
export const binarySearchPerformanceTest = () => {
  const arr = [10, 20, 30, 40, 50, 60, 70, 80, 90, 100, 150, 200, 300, 400];
  console.time('binarySearch1Time');
  for (let i = 0; i < 100 * 10000; i++) {
    binarySearch1(arr, 30);
  }
  console.timeEnd('binarySearch1Time'); 


  console.time('binarySearch2Time');
  for (let i = 0; i < 100 * 10000; i++) {
    binarySearch2(arr, 30);
  }
  console.timeEnd('binarySearch2Time'); 
}

输出结果：

• binarySearch1Time: 12.342041015625 ms
• binarySearch2Time: 25.17919921875 ms

二分查找复杂度

二分查找算法最好的情况是中间项就是目标，此时复杂度为 O(1)。二分查找每次比较能消除一半的剩余项，可以计算最多的比较次数得到该算法的最差复杂度。第一次比较后剩 n/2，第二次比较后剩余 n/4，直到 n/8，n/16，n/2i 等等。当 n/2i = 1 时，二分结束。所以

所以二分查找算法最多比较 次，复杂度也就是 ， 这是一个比 O(n) 算法还要优秀的算法。但要注意，在上述的递归版实现中，默认的栈使用是会消耗内存的，复杂度不如循环版。

二分查找看起来很好，但如果 n 很小，就不值得去排序再使用二分，此时直接使用顺序查找可能复杂度还更好。此外，对于很大数据集，对其排序很耗时和耗内存，那么直接采用顺序查找复杂度可能也更好。好在实际项目中大量的数据集即不多也不少，非常适合二分查找。