二分查找

题目描述

在一个排序数组中，快速查找指定元素，返回该下标，如果没有，则返回 -1。

二分查找，有很多变种题，例如找第一个大于等于指定数的下标，最后一个大于等于指定数，第一个小于等于指定数的下标，最后小于等于指定数的下标等等。但万变不离其宗都是关键词 排序 与 二分查找。

关键词

排序 二分查找 折半查找

思路

• 数组已经排好序，一般是基础条件。
• 设置两个指针 left ，right，分别指向头部和尾部。
• 每次算当前查找范围的中间下标 middle = Math.floor(right - left) / 2 ，判断 target 与 nums[middle] 的值大小。
• 比 nums[middle] 大，则接下来查找范围改为 [middle + 1, right]。
• 比 nums[middle] 小，则接下来查找范围改为 [left, middle - 1]。
• 与 nums[middle] 相等，则返回 middle。
• 遍历完了，都没有，则返回 -1。

一图胜千言

代码

const binarySearch = function(nums, target) {
  const n = nums.length;
  let left = 0;
  let right = n - 1;
  while (left <= right) {
    let middle = Math.floor((right - left)) + left;
    if (nums[middle] > target) {
      right = middle - 1;
    } else if (nums[middle] < target) {
      left = middle + 1;
    } else {
      return middle;
    }
  }
  return -1;
}

复杂度分析

• 时间复杂度：O(logN)
• 空间复杂度：O(1)