二分搜索

::: Tip 技巧

[left,right] 循环不变量： while 里面的值要符合定义的区间 mid 加减也要符合区间定义

• 最基本的二分查找算法
• 寻找左侧边界的二分查找
• 寻找右侧边界的二分查找

二分算法可以用来查找任何满足同一性质的区间的边界。

每次更新区间后保证目标在搜索区间[l,r]内 :::

框架

int binarySearch(int[] nums, int target) {
    int left = 0, right = ...;

    while(...) {
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) {
            ...
        } else if (nums[mid] < target) {
            left = ...
        } else if (nums[mid] > target) {
            right = ...
        }
    }
    return ...;
}

704. 二分查找 (opens new window)

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */

// 基础版二分搜索 注意搜索的区间 缺点：类似[1,2,2,2,2,3] 虽然能找到目标值 2  但是无法找到第一次出现2的 而是之间位置的2索引
var search = function (nums, target) {
  let left = 0
  let right = nums.length - 1
  // [left,right]
  while (left <= right) {
    const mid = Math.floor(left + (right - left) / 2)
    if (nums[mid] === target) {
      return mid
    } else if (target > nums[mid]) {
      left = mid + 1 // [mid+1,right]
    } else if (target < nums[mid]) {
      right = mid - 1 // [left,mid-1]
    }
  }

  return -1
}

寻找左侧边界的二分查找

// [1,2,2,2,2,3] target 2 return 1 返回左边第一个2

var leftSearch = function (nums, target) {
  if (nums.length === 0) {
    return -1
  }
  let left = 0
  let right = nums.length - 1

  while (left <= right) {
    const mid = Math.floor(left + (right - left) / 2)
    //
    if (target > nums[mid]) {
      left = mid + 1 // 会存在越界
    } else if (target < nums[mid]) {
      right = mid - 1
    } else if (target === nums[mid]) {
      right = mid - 1
    }
  }
  // 判断是否越界了 越界这块有点模糊了
  if (left === nums.length) {
    return -1
  }

  return nums[left] === target ? left : -1
}

寻找右侧边界的二分查找

function rightBoundSearch(nums, target) {
  if (nums.length === 0) {
    return -1
  }
  let left = 0
  let right = nums.length - 1

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

  if (right < 0) {
    return -1
  }
  return target === nums[right] ? right : -1
}

34. 在排序数组中查找元素的第一个和最后一个位置 (opens new window)

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
// 左侧二分查找
var leftSearch = function (nums, target) {
  if (nums.length === 0) {
    return -1
  }
  let left = 0
  let right = nums.length - 1

  while (left <= right) {
    const mid = Math.floor(left + (right - left) / 2)
    //
    if (target > nums[mid]) {
      left = mid + 1 // 会存在越界
    } else if (target < nums[mid]) {
      right = mid - 1
    } else if (target === nums[mid]) {
      right = mid - 1
    }
  }
  // 判断是否越界了 越界这块有点模糊了
  if (left === nums.length) {
    return -1
  }

  return nums[left] === target ? left : -1
}
// 右侧二位查找
function rightBoundSearch(nums, target) {
  if (nums.length === 0) {
    return -1
  }
  let left = 0
  let right = nums.length - 1

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

  if (right < 0) {
    return -1
  }
  return target === nums[right] ? right : -1
}
var searchRange = function (nums, target) {
  return [leftSearch(nums, target), rightBoundSearch(nums, target)]
}