JavaScript如何对对象数组按name、number字段实现binary search

前置要求 #

二分查找的核心前提是数组已按你要查询的字段完成排序，未排序的数组无法直接使用二分查找。

首先提供按指定字段排序的示例代码：

// 按name字段排序（字符串字典序）
const sortedByName = array.sort((a, b) => a.name.localeCompare(b.name))

// 按number字段排序（数字大小序）
const sortedByNumber = array.sort((a, b) => a.number - b.number)

通用二分查找函数实现 #

该函数支持传入排序后的数组、查询字段、目标值，找到则返回匹配的对象，未找到返回null：

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

  while (left <= right) {
    // 取中间索引，避免数值溢出
    const mid = Math.floor(left + (right - left) / 2)
    const midVal = sortedArr[mid][searchKey]

    if (midVal === target) {
      // 找到匹配项，返回完整对象
      return sortedArr[mid]
    }

    // 区分字符串和数字的比较逻辑
    if (typeof midVal === 'string') {
      if (midVal.localeCompare(target) < 0) {
        // 中间值小于目标值，到右半区查找
        left = mid + 1
      } else {
        // 中间值大于目标值，到左半区查找
        right = mid - 1
      }
    } else {
      if (midVal < target) {
        left = mid + 1
      } else {
        right = mid - 1
      }
    }
  }
  // 遍历完成未找到匹配项
  return null
}

使用示例 #

// 1. 按name字段查找
const sortedByName = array.sort((a, b) => a.name.localeCompare(b.name))
const alexResult = binarySearch(sortedByName, 'name', 'alex')
console.log(alexResult) // 输出 {name:'alex', number:36783712773}

// 2. 按number字段查找
const sortedByNumber = array.sort((a, b) => a.number - b.number)
const gabeResult = binarySearch(sortedByNumber, 'number', 99938873)
console.log(gabeResult) // 输出 {name:'gabe', number:99938873}

补充说明 #

• 如果数组中存在多个同字段值的对象，上述函数会返回匹配到的其中一个，若需要收集所有匹配项，可在找到匹配索引后，向左右遍历收集所有同值对象即可。
• 如果数组是固定不变的，仅需要做一次排序即可反复调用二分查找，时间复杂度为O(log n)，数据量越大性能优势越明显。

内容的提问来源于stack exchange，提问作者Azan Korejo