二分搜索中字符串如何通过< >运算符比较？代码解析疑问

问题描述 #

我写的二分搜索代码能正常运行，但对每行代码的作用有困惑，尤其搞不懂递归时，单字符字符串数组里的target和arr[middle]为什么能用大于/小于运算符比较，求解析。

代码示例 #

function search(arr, target, start = 0, end = arr.length - 1) {
  console.log(start, end)

  if (start > end) {
    console.log('Not found!');
    return -1;
  }

  const middle = Math.floor((start + end) / 2);

  if (arr[middle] === target) {
    console.log(`${target} Found at index ${middle}`);
    return middle;
  }

  if (arr[middle] > target) {
    return search(arr, target, start, middle - 1);
  }

  if (arr[middle] < target) {
    return search(arr, target, middle + 1, end);
  }
}

const arr = ['a', 'b', 'c', 'x', 'y', 'z'];
console.log(search(arr, 'b'));

一、代码逐行解析 #

• function search(arr, target, start = 0, end = arr.length - 1)：定义递归式二分搜索函数，参数分别是待搜索的有序数组arr、目标值target，以及搜索范围的起始/结束索引（默认覆盖整个数组）
• console.log(start, end)：打印当前搜索的索引范围，方便调试时观察搜索范围的收缩过程
• if (start > end) { ... }：递归终止条件——如果起始索引超过结束索引，说明整个搜索范围已排查完毕，目标值不存在，打印提示后返回-1
• const middle = Math.floor((start + end) / 2)：计算当前搜索范围的中间位置索引，用Math.floor向下取整，保证得到合法的整数索引
• if (arr[middle] === target) { ... }：如果中间位置的元素正好是目标值，说明找到结果，打印目标值的索引后返回该索引
• if (arr[middle] > target) { ... }：如果中间元素比目标值"大"，说明目标值在左半范围，递归调用函数缩小范围到start到middle-1
• if (arr[middle] < target) { ... }：如果中间元素比目标值"小"，说明目标值在右半范围，递归调用函数缩小范围到middle+1到end
• 最后两行：定义按字母顺序排列的单字符数组，调用搜索函数查找'b'并打印返回的索引结果

二、单字符字符串能用> / <比较的核心原因 #

在JavaScript里，字符串的大小比较是基于**Unicode码点（UTF-16编码的数值）**进行的：

1. 每个字符都对应唯一的Unicode码点，比如'a'的码点是97，'b'是98，'x'是120，'z'是122，数值顺序和字母顺序完全一致
2. 对于单字符字符串，直接比较两个字符的码点数值大小即可，所以'a' < 'b'、'z' > 'x'这类判断都成立
3. 你的数组是严格按字母顺序排列的，恰好匹配Unicode码点的递增规律，满足二分搜索对"有序数组"的要求，因此比较运算符能正确收缩搜索范围

内容的提问来源于stack exchange，提问作者Jose Salduna