基础 查找

• 顺序查找
• 二分查找
• 插值查找
• 斐波那契查找

// ArrayList.sort.js
const ArrayList = require("./ArrayList.js");

module.exports = ArrayList;

ArrayList.prototype.sort = function (callback) {
  this.arr.sort(callback);
};

顺序查找

从数组的第一个元素开始，逐个比较直到找到目标元素或遍历完整个数组。

ArrayList.prototype.sequentialSearch = function (item) {
  const arr = this.arr;
  for (let i = 0; i < arr.length; i++) {
    if (item == arr[i]) {
      return i;
    }
  }
  return -1;
};

二分查找 (重点)

每次将数组分成两半，并在中间元素与目标值进行比较。时间复杂度为 (O(\log n))。

// 二分查找 需要有序列表
ArrayList.prototype.binarySearch = function (target) {
  this.sort((a, b) => a - b);
  const arr = this.arr;
  let left = 0;
  let right = arr.length - 1;
  while (left <= right) {
    let mid = left + Math.floor((right - left) / 2);
    if (arr[mid] == target) {
      return mid; // 找到了返回
    } else if (arr[mid] < target) {
      left = mid + 1; // 收缩
    } else if (arr[mid] > target) {
      right = mid - 1; // 收缩
    }
  }
  // left > right 没找到
  return -1;
};

插值查找

假设数据是均匀分布的，通过计算目标值在数组中的估计位置来减少搜索范围。平均情况下时间复杂度为 (O(\log \log n))

function interpolationSearch(arr, target) {
  let low = 0;
  let high = arr.length - 1;

  while (low <= high && target >= arr[low] && target <= arr[high]) {
    if (low === high) {
      if (arr[low] === target) return low;
      return -1;
    }

    // 计算中间位置
    let pos = Math.floor(low + ((target - arr[low]) * (high - low)) / (arr[high] - arr[low]));

    if (arr[pos] === target) {
      return pos; // 找到目标值，返回索引
    } else if (arr[pos] < target) {
      low = pos + 1; // 在右半部分继续查找
    } else {
      high = pos - 1; // 在左半部分继续查找
    }
  }

  return -1; // 没有找到目标值
}

斐波那契查找

利用斐波那契数列来分割数组，并在每次比较后减少搜索范围。斐波那契查找适用于有序数组，并且在某些情况下比二分查找更高效。

function fibonacciSearch(arr, target) {
  let fib2 = 0; // (m-2)'th Fibonacci number
  let fib1 = 1; // (m-1)'th Fibonacci number
  let fibM = fib2 + fib1; // m'th Fibonacci number

  // 扩展数组到长度为 fibM
  while (fibM < arr.length) {
    fib2 = fib1;
    fib1 = fibM;
    fibM = fib2 + fib1;
  }

  let offset = -1;

  // 在数组中进行查找
  while (fibM > 1) {
    let i = Math.min(offset + fib2, arr.length - 1);

    if (arr[i] < target) {
      fibM = fib1;
      fib1 = fib2;
      fib2 = fibM - fib1;
      offset = i;
    } else if (arr[i] > target) {
      fibM = fib2;
      fib1 = fib1 - fib2;
      fib2 = fibM - fib1;
    } else {
      return i; // 找到目标值，返回索引
    }
  }

  // 检查最后一个元素是否是目标值
  if (fib1 && arr[offset + 1] === target) {
    return offset + 1;
  }

  return -1; // 没有找到目标值
}

// ArrayList.sort.test.js
let arr = new ArrayList(16);
console.log("顺序查找");
arr.init();
arr.shuffle();
console.log(arr.toString());
console.log(arr.sequentialSearch(8));

console.log("二分查找");
arr.init();
arr.sort();
console.log(arr.toString());
console.log(arr.binarySearch(8));