您现在的位置是:首页 >技术教程 >【数据结构与算法】二分查找网站首页技术教程

【数据结构与算法】二分查找

前端程序员小张 2024-06-14 17:17:53
简介【数据结构与算法】二分查找

【数据结构与算法】二分查找(力扣704、35、34题解)

写在前面

?这里是前端程序员小张!

?人海茫茫,感谢这一秒你看到这里。希望我的文章对你的有所帮助!

?愿你在未来的日子,保持热爱,奔赴山海!

一、 相关概念

查找过程

假设表中元素是按升序排序,将表中间位置记录的关键字与查找关键字比较,如果两者相等,则查找成功;否则利用中间位置记录将表分成前、后两个子表,如果中间位置记录的关键字大于查找关键字,则进一步查找前一子表,否则进一步查找后一子表。重复以上过程,直到找到满足条件的记录,使查找成功,或直到子表不存在为止,此时查找不成功

算法要求

  • 必须采用顺序存储结构
  • 必须按关键字大小有序排列

二、 二分查找框架

var binarySearch = function (nums, target) {
  int left = 0, right = ...;

  while(...) {
      int mid = left + Math.floor((right - left) / 2);
      if (nums[mid] == target) {
          ...
      } else if (nums[mid] < target) { //若中间位置的关键字小于关键字,则查找后一子表
          left = ...
      } else if (nums[mid] > target) { //若中间位置的关键字大于关键字,则查找前一子表
          right = ...
      }
  }
  return ...;
}

三、力扣相关题

3.1 二分查找(704)

题目描述

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

示例 1:

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

示例 2:

输入: nums = [-1,0,3,5,9,12], target = 2
输出: -1
解释: 2 不存在 nums 中因此返回 -1

提示:

  1. 你可以假设 nums 中的所有元素是不重复的。
  2. n 将在 [1, 10000]之间。
  3. nums 的每个元素都将在 [-9999, 9999]之间。

题解

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var search = function(nums, target) {
  // right是数组最后一个数的下标,nums[right]在查找范围内,是左闭右闭区间
  let left = 0, right = nums.length - 1;
  // 当left=right时,由于nums[right]在查找范围内,所以要包括此情况
  while(left <= right) {
    // 表的中间位置
      const middle = Math.floor((right - left) / 2 ) +left;
      const num = nums[middle];
      if(num == target) {
          return middle
      } else if (num > target) {
          right =  middle - 1;
      } else {
          left = middle + 1
      }
  }
  return -1
};

3.2 搜索插入位置 (35)

题目描述

给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。

请必须使用时间复杂度为 O(log n) 的算法。

示例 1:

输入: nums = [1,3,5,6], target = 5
输出: 2

示例 2:

输入: nums = [1,3,5,6], target = 2
输出: 1

示例 3:

输入: nums = [1,3,5,6], target = 7
输出: 4

题解

var searchInsert = function(nums, target) {
    const n = nums.length;
    let left = 0, right = n - 1, ans = n;
    while (left <= right) {
        let mid = Math.floor((right - left) / 2) + left;
        if (target <= nums[mid]) {
            ans = mid;
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    return ans;
};

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

题目描述

给你一个按照非递减顺序排列的整数数组 nums,和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。

如果数组中不存在目标值 target,返回 [-1, -1]。

你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。

示例 1:

输入:nums = [5,7,7,8,8,10], target = 8
输出:[3,4]

示例 2:

输入:nums = [5,7,7,8,8,10], target = 6
输出:[-1,-1]

示例 3:

输入:nums = [], target = 0
输出:[-1,-1]

题解

  • 数组已经排序,我们可以使用二分查找
  • target开始位置 就是我们要找数组中第一个target的位置,二分查找中, 即为在数组中寻找第一个等于 target 的下标
  • target结束位置 我们要找数组中第一个大于target的位置减1,二分查找中,即为在数组中寻找第一个大于 target 的下标,然后将下标减一
/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */

const binarySearch = (nums, target, lower) => {
   // 将代码复用,如果 lower 为 true,则查找第一个等于 target 的下标,否则查找第一个大于 target 的下标。
    let left = 0, right = nums.length - 1, ans = nums.length;
    while (left <= right) {
        const middle = Math.floor((right - left) / 2) + left;
        if (nums[middle] > target || (lower && nums[middle] == target)) {
            right = middle - 1;
            ans = middle;
        } else {
            left = middle + 1;
        }
    }
    return ans;
}

var searchRange = function (nums, target) {
    let ans = [-1, -1];
    const leftIdx = binarySearch(nums, target, true)
    const rightIdx = binarySearch(nums, target, false) - 1
    if (leftIdx <= rightIdx && rightIdx < nums.length && nums[leftIdx] === target && nums[rightIdx] === target) {
        ans = [leftIdx, rightIdx];
    }
    return ans;
};

写在最后

二分查找的大体思路很容易懂,但具体的细节还是很细碎的,更多细节推荐看代码随想录 —二分查找

风语者!平时喜欢研究各种技术,目前在从事后端开发工作,热爱生活、热爱工作。