二分查找

查找某个数

搜索区间不管是闭区间[left, right]，还是左闭右开区间[left, right)，只要没查询到都是返回-1。

/**
 * @param {number[]} nums
 * @param {number} target
 * @returns {number}
 */
const binarySearch1 = function (nums, target) {
  let left = 0;
  let right = nums.length;
  while (left < right) {
    const mid = left + Math.floor((right - left) / 2);
    if (nums[mid] < target) {
      left = mid + 1;
    } else if (nums[mid] > target) {
      right = mid;
    } else if (nums[mid] === target) {
      return mid;
    }
  }
  return -1;
};

/**
 * @param {number[]} nums
 * @param {number} target
 * @returns {number}
 */
const binarySearch2 = function (nums, target) {
  let left = 0;
  let right = nums.length - 1;
  while (left <= right) {
    const 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) {
      return mid;
    }
  }
  return -1;
};

查找左侧边界

如果target不存在，搜索左侧边界的二分搜索的left结果值是大于target的最小索引（如果没有大于target的值，left的值为数组最大索引加1）。因此如果想让target不存在时返回-1，需要在返回的时候额外判断一下nums[left]是否等于target，如果不等于，就说明target不存在。需要注意的是，访问数组索引之前要保证索引不越界。（两种搜索区间一样）

/**
 * @param {number[]} nums
 * @param {number} target
 * @returns {number}
 */
const leftBound1 = function (nums, target) {
  let left = 0;
  let right = nums.length;
  while (left < right) {
    const mid = left + Math.floor((right - left) / 2);
    if (nums[mid] < target) {
      left = mid + 1;
    } else if (nums[mid] > target) {
      right = mid;
    } else if (nums[mid] === target) {
      right = mid;
    }
  }
  // 判断 target 是否存在于 nums 中
  if (left < 0 || left >= nums.length) {
    return -1;
  }
  // 判断一下 nums[left] 是不是 target
  return nums[left] === target ? left : -1;
};

/**
 * @param {number[]} nums
 * @param {number} target
 * @returns {number}
 */
const leftBound2 = function (nums, target) {
  let left = 0;
  let right = nums.length - 1;
  while (left <= right) {
    const 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) {
      right = mid - 1;
    }
  }
  // 判断 target 是否存在于 nums 中
  if (left < 0 || left >= nums.length) {
    return -1;
  }
  // 判断一下 nums[left] 是不是 target
  return nums[left] === target ? left : -1;
};

查找右侧边界

/**
 * @param {number[]} nums
 * @param {number} target
 * @returns {number}
 */
const rightBound1 = function (nums, target) {
  let left = 0;
  let right = nums.length;
  while (left < right) {
    const mid = left + Math.floor((right - left) / 2);
    if (nums[mid] < target) {
      left = mid + 1;
    } else if (nums[mid] > target) {
      right = mid;
    } else if (nums[mid] === target) {
      left = mid + 1;
    }
  }
  // while 的结束条件是 right === left
  if (left - 1 < 0 || left - 1 >= nums.length) {
    return -1;
  }
  return nums[left - 1] === target ? left - 1 : -1;
};

/**
 * @param {number[]} nums
 * @param {number} target
 * @returns {number}
 */
const rightBound2 = function (nums, target) {
  let left = 0;
  let right = nums.length - 1;
  while (left <= right) {
    const 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;
    }
  }
  // while 的结束条件是 right === left - 1，且现在在求右边界
  if (left - 1 < 0 || left - 1 >= nums.length) {
    return -1;
  }
  return nums[left - 1] === target ? left - 1 : -1;
};

参考文章：labuladong 的算法笔记 (opens new window)