Binary Search

[campcc]

二分查找的一些技巧：

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

    while (left <= right) {
        var mid = left + Math.floor((right - left) / 2);
        if (nums[mid] === target) return mid;
        if (nums[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return -1;
};

// 1. 计算 mid 时防止溢出
// 我们可以简单比较下 (right - left) / 2 的情况，两者虽然结果相同，但如果 left 和 right 太大，直接相加可能导致溢出
var mid = left + (right - left) / 2;

// 2. 终止条件的判断可以想象为区间的开闭
// 右边界 right 一般是数组的 length - 1，因为索引大小 nums.length 是越界的
// 如果是 left <= right，终止条件是 left = right + 1，对应的就是 [right, right + 1] 这个闭区间
while(left <= right) {
  // code ...
}
// 如果是 left < right，终止条件是 left === right，对应区间为 [right, right]，这种情况会少遍历一个元素
while(left < right) {
  // code ...
}

// 3. 二分搜索的区间判断需要考虑已搜索的元素 mid
// 我们的初始区间为 [left, right]，并且 mid 已经判断过了，那么下次搜索的区间就是 [left, mid - 1]，[mid + 1, right]
// 如果目标元素比 mid 大，我们搜索右区间，left = mid + 1, right = right
// 如果目标元素比 mid 小，我们搜索左区间，left = left, right = mid - 1
if (nums[mid] < target) {
  left = mid + 1;
} else {
  right = mid - 1;
}

基于上述的区间思路，我们可以很容易写出寻找左侧边界或右侧边界的二分查找，关键点就是，

1. 搜索到 target 时，先不急着返回，而是收缩左右边界
2. 缩小边界可能会导致越界问题，我们在返回时加上越界判断即可

寻找左侧边界的二分查找，

function binarySearchLeft(nums, target) {
  var left = 0;
  var right = nums.length - 1;
  while (left <= right) {
    var mid = left + Math.floor((right - left) / 2);
    if (nums[mid] === target) {
      right = mid - 1; // 收缩右侧边界
    } else if (nums[mid] > target) {
      right = mid - 1;
    } else if (nums[mid] < target) {
      left = mid + 1;
    }
  }
  // 越界判断，检查 left 是否越界
  if (left >= nums.length || nums[left] !== target) return -1;

  return left;
}

寻找右侧边界的二分查找，

function binarySearchRight(nums, target) {
  var left = 0;
  var right = nums.length - 1;
  while (left <= right) {
    var mid = left + Math.floor((right - left) / 2);
    if (nums[mid] === target) {
      left = mid + 1; // 收缩左侧边界
    } else if (nums[mid] > target) {
      right = mid - 1;
    } else if (nums[mid] < target) {
      left = mid + 1;
    }
  }
  // 越界判断，检查 right 是否越界
  if (right < 0 || nums[mid] !== target) return -1;

  return right;
}