二分查找（Binary Search）

1.二分查找的介绍

二分查找（Binary Search）是一种用于在有序数组中快速查找特定元素的搜索算法。

它的核心思想是通过不断将搜索范围减半，来快速定位目标元素。

以下是详细的步骤：

  1. 初始化左右边界： 首先，确定搜索范围的左边界 left 和右边界 right。初始时，left 设置为数组的起始位置（通常是 0），right 设置为数组的末尾位置（数组长度减 1）。

  2. 进入循环： 使用一个循环来不断缩小搜索范围，直到找到目标元素或确定它不存在。循环条件是 left 小于等于 right。

  3. 计算中间索引： 在每次循环迭代中，计算中间索引 mid，通常通过 (left + right) / 2 来获取。这个索引指向当前搜索范围的中间元素。

  4. 比较中间元素： 将中间元素与目标元素进行比较：

    • 如果中间元素等于目标元素，那么找到了目标，返回 mid。
    • 如果中间元素小于目标元素，说明目标元素可能在右半部分，将 left 更新为 mid + 1。
    • 如果中间元素大于目标元素，说明目标元素可能在左半部分，将 right 更新为 mid - 1。

  5. 重复步骤 3 和 4： 继续在新的搜索范围内执行步骤 3 和 4，直到找到目标元素或确定它不存在。

  6. 返回结果： 如果找到目标元素，返回它的索引；否则，返回 -1 表示未找到。

下面是一个 JavaScript 示例，演示如何实现二分查找：

function binarySearch(arr, target) {
  let left = 0;
  let right = arr.length - 1;

  while (left <= right) {
    const mid = Math.floor((left + right) / 2);

    if (arr[mid] === target) {
      return mid; // 找到了目标元素，返回索引
    } else if (arr[mid] < target) {
      left = mid + 1; // 目标在右半部分
    } else {
      right = mid - 1; // 目标在左半部分
    }
  }

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

总之，二分查找是一种高效的查找算法，特别适用于大型有序数组，

因为它可以在 O(log n) 的时间复杂度内找到目标元素，

其中 n 是数组的长度。这远比线性查找（O(n)）要快。

但要注意，前提是数组必须是有序的，否则算法将无法正确工作。

2. 二分查找的示例


// 二分查找，寻找数字7的索引
const numArr = [1, 2, 3, 4, 5, 6, 7, 8, 9]
/*******************************************************************************************************
* 1.找到中间的索引值 5分开，[1, 2, 3, 4] 5 [6, 7, 8, 9,10]
  2.和中间的数字进行对比，需要找的数字7大于5，则在右边找
  3.[6, 7] 8 [9, 10],找到中间的索引值8,需要找的数字7小于8，则在左边找
  4.[6] ,7,找到中间的索引值7,找到
*/

function searchIndex(arr, searchValue, compareFn) {
  compareFn = compareFn || function (a, b) { return a - b };
  let firstIndex = 0, lastIndex = arr.length - 1;

  while (firstIndex <= lastIndex) {
    let middleIndex = Math.ceil((firstIndex + lastIndex) / 2);
    const compareResult = compareFn(arr[middleIndex], searchValue);

    if (compareResult === 0) {
      return middleIndex
    } else if (compareResult > 0) {
      lastIndex = middleIndex - 1
    } else if (compareResult < 0) {
      firstIndex = middleIndex + 1
    }
  }
  return -1
}

const index = searchIndex(numArr, 7);
console.log(index);

/*******************************************************************************************************
* 目前有数组50000个数据，ids：10000个，查找详情
*/

const arr = Array.from({ length: 50000 }, (item, idx) => {
  return { id: idx, name: 'any string', age: 'random number' };
});
// [{id:0},{id:1},{id:2},{id:3},{id:4}]


const ids = Array.from({ length: 10000 }, (item, idx) => {
  // 0~50000 之间的整数
  return Math.ceil(Math.random() * 50000);
});
// [1,4,5]


function findDetail(arr, ids) {
  // 查id的每个详细数据返回

  if (!ids || !ids.length) {
    return null;
  }

  const result = ids.map(id => {
    const item = findItem(arr, id);
    return item;
  })

  return result;
}

function findItem(arr, id) {
  const index = searchIndex(arr, id, (item, id) => item.id - id);
  return arr[index];
}

const listDetails = findDetail(arr, ids);
console.log(listDetails);
Contributors: masecho