【二分查找】如何用最省内存的方式实现快速查找功能

[slogeor]

[slogeor]

问题描述

假设我们有 1000 万个整数数据，每个数据占 8 个字节，如何设计数据结构和算法，快速判断某个数据是否出现在这 1000 万数据中？

我们希望这个功能不要占用太多的内存空间，最多不要超过 100MB，应该如何做呢？

问题解析

1000 万个整数数据，每个数据占 8 个字节，将这些数据存储在数组中，内存占用差不多是 (1000 * 10000 * 8) / (1000 * 1000) = 80 MB，符合内存的限制

对这 1000 万的数据进行排序，然后利用二分查找算法，查到某个数据是否出现这 1000 万数据中。

时间复杂度分析

排序算法使用快速排序，时间复杂度是 O(n * logn)
二分查找的时间复杂度是 O(logn)
故时间复杂度是 O(n * logn)

[slogeor]

循环法

function binarySearch(arr = [], target) {
  // 异常
  if (arr.length === 0) return -1;

  var low = 0;
  var high = arr.length - 1;

  while (low <= high) {
    var mid = Math.floor((low + high) / 2);
    if (arr[mid] < target) {
      low = mid + 1;
    } else if (arr[mid] > target) {
      high = mid - 1;
    } else if (arr[mid] === target) {
      return mid;
    }
  }
  return -1;
}
// binarySearch([1,3,5,7,9],1) 1
// binarySearch([1,3,5,7,9],9) 4
// binarySearch([1,3,5,7,9],11) -1

[slogeor]

递归法

/**
 * 二分查找之递归法
 * @param {Array} arr
 * @param {number} target
 * @param {number} low
 * @param {number} high
 * @returns {number}
 */
function binarySearch2(arr = [], target, low, high) {
  if (arr.length === 0) return -1;
  var mid = Math.floor((low + high) / 2);

  // 递归结束条件
  if (low > high) return - 1;

  if (arr[mid] < target) {
    low = mid + 1;
  } else if (arr[mid] > target) {
    high = mid - 1;
  } else if (arr[mid] === target) {
    return mid;
  }
  return binarySearch2(arr, target, low, high);
}
// binarySearch2([1,3,5,7,9],11, 0, 4);  -1
// binarySearch2([1,3,5,7,9],1, 0, 4);  0
// binarySearch2([1,3,5,7,9],9, 0, 4);  4