跳到主要内容

704-二分查找

  • 二分查找（Binary Search）算法，也叫折半查找算法

  • 每次都通过跟区间的中间元素对比，将待查找的区间缩小为之前的一半，直到找到要查找的元素，或者区间被缩小为 0

  • 时间复杂度O(logn)

1、凡有序，必二分

2、凡二分，时间复杂度必包含 O(logn)

题目：给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

示例 1:

text
输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4

循环​

js
function BinarySearch(arr, target) {
  if (arr.length <= 1) return -1;
  // 开始位置
  let startIndex = 0;
  // 结束位置
  let endIndex = arr.length - 1;

  while (startIndex <= endIndex) {
    // 中间下标
    const midIndex = Math.floor((startIndex + endIndex) / 2);
    const midValue = arr[midIndex];
    if (target < midValue) {
      // 目标值较小，则继续在左侧查找
      endIndex = midIndex - 1;
    } else if (target > midValue) {
      // 目标值较大，则继续在右侧查找
      startIndex = midIndex + 1;
    } else {
      // 相等,返回
      // target === arr[midIndex]
      return midIndex;
    }
  }
  return -1;
}

递归​

js
function BinarySearch(nums, target, startIndex, endIndex) {
  if (startIndex > endIndex) {
    return -1;
  }
  var midIndex = Math.floor((startIndex + endIndex) / 2);
  const midValue = arr[midIndex];
  if (target == midValue) {
    return midIndex;
  } else if (target < midValue) {
    endIndex = midIndex - 1;
    return BinarySearch(nums, target, startIndex, endIndex);
  } else {
    startIndex = midIndex + 1;
    return BinarySearch(nums, target, startIndex, endIndex);
  }
}