WSの小屋

原理

二分查找（Binary Search）算法，也叫折半查找算法。二分查找的思想非常简单，有点类似分治的思想。二分查找针对的是一个有序的数据集合，每次都通过跟区间的中间元素对比，将待查找的区间缩小为之前的一半，直到找到要查找的元素，或者区间被缩小为 0。

二分查找的过程就像上图一样，如果中间值大于查找值，则往数组的左边继续查找，如果小于查找值这往右边继续查找。二分查找的思想虽然非常简单，但是查找速度非常长，二分查找的时间复杂度为O(logn)。虽然二分查找的时间复杂度为O(logn)但是比很多O(1)的速度都要快，因为O(1)可能标示一个非常大的数值，比例O(1000)。我们来看一张二分查找与遍历查找的效率对比图。

二分查找依赖数组结构

二分查找需要利用下标随机访问元素，如果我们想使用链表等其他数据结构则无法实现二分查找

二分查找针对的是有序数据

二分查找需要的数据必须是有序的。如果数据没有序，我们需要先排序，排序的时间复杂度最低是 O(nlogn)。所以，如果我们针对的是一组静态的数据，没有频繁地插入、删除，我们可以进行一次排序，多次二分查找。这样排序的成本可被均摊，二分查找的边际成本就会比较低。

但是，如果我们的数据集合有频繁的插入和删除操作，要想用二分查找，要么每次插入、删除操作之后保证数据仍然有序，要么在每次二分查找之前都先进行排序。针对这种动态数据集合，无论哪种方法，维护有序的成本都是很高的。

所以，二分查找只能用在插入、删除操作不频繁，一次排序多次查找的场景中。针对动态变化的数据集合，二分查找将不再适用。

数据量太小不适合二分查找

如果要处理的数据量很小，完全没有必要用二分查找，顺序遍历就足够了。比如我们在一个大小为 10 的数组中查找一个元素，不管用二分查找还是顺序遍历，查找速度都差不多，只有数据量比较大的时候，二分查找的优势才会比较明显。

数据量太大不适合二分查找

二分查找底层依赖的是数组，数组需要的是一段连续的存储空间，所以我们的数据比较大时，比如1GB，这时候可能不太适合使用二分查找，因为我们的内存都是离散的，可能电脑没有这么多的内存。

代码实现

循环

ts 复制代码 
function bsearch(nums: number[], value: number) {
  let low = 0;
  let high = nums.length - 1;

  while (low <= high) {
    let mid = low + Math.floor((high - low) / 2);
    if (nums[mid] > value) {
      high = mid - 1;
    } else if (nums[mid] < value) {
      low = mid + 1;
    } else {
      return mid;
    }
  }
}

递归

ts 复制代码 
function recursiveBsearch(nums: number[], value: number) {
  let low = 0;
  let high = nums.length - 1;
  let mid = low + Math.floor((high - low) / 2);

  if (nums[mid] == value) {
    return mid;
  }
  if (nums[mid] > value) {
    high = mid - 1;
  } else if (nums[mid] < value) {
    low = mid + 1;
  }
  if (low < high) {
    return recursiveBsearch(nums.slice(low, high), value);
  }
}

原文

图文并茂带你入门二分查找算法

Comments | 0条评论