使用二分查找法寻找数组中的目标值与上下界

• 在我们平常的数组元素查找算法中，假设已知数组内数字的排序是由小到大，其余不设条件，那么使用二分法查找是算法复杂度最小的方式。
• 同时，在可以寻找到目标值的时候，还可以根据二分查找的套路，去找到目标值的上下界。上界就是找到那个大于目标值，并且又是最接近目标值的那个数，比如：

Number[]: [1,2,4,5]
target: 3

// 那么在该例子中，上界值就是 4 ，因为 4 大于 3 且又是最接近 3 的那个数
复制代码

寻找上下界在很多场景都有运用，比如在寻找最长递增子序列的这个场景中，同时 vue3 的 diff 算法也是采用了寻找上界的二分查找法。

(一): 寻找目标值

// 二分查找法寻找目标值
  function binarySearch(arr, target) {
    let left = 0;
    let right = arr.length - 1;
    while (left < right) {
      // 获取中位下标
      let middle = Math.floor(left + (right - left / 2));
      const middleEle = arr[middle]
      // 假如已经找到
      if (middleEle === target) {
        return middle
        // 假如中位数小于目标，那么就代表中位数左侧的值都不满足，左侧下标修改为中位下标 + 1
      } else if (middleEle < target) {
        left = middle + 1;
        // 如上逻辑
      } else {
        right = middle - 1
      }
    }
    return -1;
  }
复制代码

(二): 寻找目标上界值

function binarySearchUpperBound(arr, target) {
    // 假如数组长度为 0 或者最后一位都不是大于 target 的，那么就代表没有找到大于该数的上界目标
    if (arr.length === 0 || arr[arr.length - 1] <= target) return -1;

    let left = 0;
    let right = arr.length - 1;
    let middle;
    while (left < right) {
      middle = Math.floor(left + (right - left) / 2);
      // 假如说中位数小于目标，那么就代表至少是 left + 1 个是可以选择的目标
      if (arr[middle] < target) {
        left = middle + 1;
      } else {
        // 假如说中位数大于等于目标，那么就代表说可选范围就是 left - middle 的范围，因为 middle 大于目标，也就是说至少
        // 在 left - middle 范围内，至少 middle 也是可以选择的目标
        right = middle
      }
    }
    // 收缩到最后肯定是 left === right，那么也就是 middle === left === right ，返回 left 也是可以的
    return middle;
  }
复制代码

(三): 寻找目标下界值

function binarySearchLowerBound(arr, target) {
    if (arr.length === 0 || arr[0] > target) return -1;
    let left = 0, right = arr.length - 1;
    let middle;
    while (left < right) {
      // 这里需要向上取整是因为在找下界的时候为了防止该种情况 target = 1 ，arr = [0, 2];
      // 那么假如是向下取整，那么 middle 是 0 ，满足 left = middle，继续死循环
      middle = Math.ceil(left + (right - left) / 2);
      // 其余逻辑和找上界一致
      if (arr[middle] > target) {
        right = middle - 1;
      } else {
        left = middle
      }
    }
  }
复制代码