如何实现对包含负值的数组进行二分查找？附代码验证

首先把你的代码整理成可读性更好的格式：

function BinarySearch(items, value) {
  var start = 0, stop = items.length - 1, mid = Math.floor((stop + start) / 2);
  while (items[mid] !== value && start < stop) {
    if (value < items[mid]) {
      stop = mid - 1;
    } else if (value > items[mid]) {
      start = mid + 1;
    }
    mid = Math.floor((stop + start) / 2);
  }
  var output = (items[mid] != value) ? -1 : mid;
  return output;
}
var arr = [5, 6, 7, 8, 9, 10, 1, -1, 2, 3];
var key = -1;
var ans = BinarySearch(arr, key);
console.log("ans is " + ans);

代码逻辑分析 #

这个实现是标准的二分查找逻辑，但它有个核心前提：输入数组必须是完全升序（或降序）排列的。而你使用的数组[5,6,7,8,9,10,1,-1,2,3]是一个非整体有序的旋转数组——它原本是升序数组，经过旋转后被拆成了两个不完全连续的升序片段，甚至中间还出现了1,-1这种局部逆序的情况，完全不符合标准二分查找的适用场景。

运行过程模拟 #

我们一步步拆解代码的执行流程：

1. 初始状态：start=0，stop=9，mid=Math.floor((0+9)/2)=4，此时items[mid]=9
2. 目标值-1 < 9，所以调整stop=4-1=3，新的mid=Math.floor((0+3)/2)=1，items[mid]=6
3. -1 < 6，继续调整stop=1-1=0，此时start=0、stop=0，循环条件start < stop不满足，退出循环
4. 检查items[mid]（此时mid=0，对应值为5）不等于目标值-1，所以返回-1

运行结果 #

最终控制台会输出 ans is -1——代码没有找到实际存在于数组索引7位置的-1，直接返回了查找失败的标识。

问题根源 #

标准二分查找的核心逻辑是通过目标值与中间值的大小关系，确定目标值必然存在的区间。但当数组不是整体有序时，这个逻辑就会失效：比如本例中，目标值-1实际上在数组的后半段，但标准二分查找会因为它小于前半段的中间值，错误地把搜索范围限制到前半段，最终错过正确的区间。要处理这类数组，需要修改二分逻辑：每次先判断哪一侧是有序的，再根据目标值是否在有序区间内来调整搜索范围。

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