当前位置: 首页 > news >正文

二分查找题目:搜索插入位置

文章目录

  • 题目
    • 标题和出处
    • 难度
    • 题目描述
      • 要求
      • 示例
      • 数据范围
  • 前言
  • 解法一
    • 思路和算法
    • 代码
    • 复杂度分析
  • 解法二
    • 思路和算法
    • 代码
    • 复杂度分析

题目

标题和出处

标题:搜索插入位置

出处:35. 搜索插入位置

难度

2 级

题目描述

要求

给定一个由不同整数组成的排序数组和一个目标值,在数组中找到目标值,并返回其下标。如果数组中没有目标值,返回它将会被按顺序插入的位置。

要求时间复杂度是 O(log n) \texttt{O(log n)} O(log n)

示例

示例 1:

输入: nums = [1,3,5,6], target = 5 \texttt{nums = [1,3,5,6], target = 5} nums = [1,3,5,6], target = 5
输出: 2 \texttt{2} 2

示例 2:

输入: nums = [1,3,5,6], target = 2 \texttt{nums = [1,3,5,6], target = 2} nums = [1,3,5,6], target = 2
输出: 1 \texttt{1} 1

示例 3:

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

数据范围

  • 1 ≤ nums.length ≤ 10 4 \texttt{1} \le \texttt{nums.length} \le \texttt{10}^\texttt{4} 1nums.length104
  • -10 4 < nums[i] < 10 4 \texttt{-10}^\texttt{4} < \texttt{nums[i]} < \texttt{10}^\texttt{4} -104<nums[i]<104
  • nums \texttt{nums} nums 中的元素各不相同并按升序排序
  • -10 4 < target < 10 4 \texttt{-10}^\texttt{4} < \texttt{target} < \texttt{10}^\texttt{4} -104<target<104

前言

这道题和「二分查找」大致相同,区别在于当数组中没有目标值时,不是返回 − 1 -1 1,而是返回目标值在数组中的插入位置,使得插入目标值之后的数组仍然按升序排序。

由于这道题和最简单的二分查找的区别只有没有找到目标值时的返回值,因此可以使用二分查找的做法,当没有找到目标值时将返回 − 1 -1 1 换成返回插入位置即可。

假设目标值 target \textit{target} target 在数组 nums \textit{nums} nums 中的插入位置是 index \textit{index} index,则为了确保插入目标值之后的数组 nums \textit{nums} nums 仍然按升序排序,应满足 nums [ index − 1 ] < target < nums [ index ] \textit{nums}[\textit{index} - 1] < \textit{target} < \textit{nums}[\textit{index}] nums[index1]<target<nums[index]。这里假设 nums [ − 1 ] = − ∞ \textit{nums}[-1] = -\infty nums[1]= nums [ n ] = + ∞ \textit{nums}[n] = +\infty nums[n]=+,其中 n n n 是数组 nums \textit{nums} nums 的长度。

low \textit{low} low high \textit{high} high 分别表示二分查找的下标范围的下界和上界,每次查找时,取 mid \textit{mid} mid low \textit{low} low high \textit{high} high 的平均数向下取整,判断下标 mid \textit{mid} mid 处的数和目标值的大小关系,调整查找的下标范围。

在二分查找的过程中,如果 nums [ mid ] < target \textit{nums}[\textit{mid}] < \textit{target} nums[mid]<target,则将 low \textit{low} low 更新为 mid + 1 \textit{mid} + 1 mid+1,因此在二分查找结束之后有 nums [ low ] ≥ target \textit{nums}[\textit{low}] \ge \textit{target} nums[low]target。当目标值不存在时,二分查找结束之后有 nums [ low ] > target \textit{nums}[\textit{low}] > \textit{target} nums[low]>target。又由于当 nums [ mid ] ≥ target \textit{nums}[\textit{mid}] \ge \textit{target} nums[mid]target 时不可能将 low \textit{low} low 更新为比 mid \textit{mid} mid 大的值,因此在二分查找结束之后有 nums [ low − 1 ] < target \textit{nums}[\textit{low} - 1] < \textit{target} nums[low1]<target

因此在二分查找结束之后有 nums [ low − 1 ] < target < nums [ low ] \textit{nums}[\textit{low} - 1] < \textit{target} < \textit{nums}[\textit{low}] nums[low1]<target<nums[low] low \textit{low} low 即为目标值在数组中的插入位置。

根据上述分析,可以得到搜索插入位置的完整过程。

low \textit{low} low high \textit{high} high 分别表示二分查找的下标范围的下界和上界,初始时 low \textit{low} low high \textit{high} high 分别为数组的最小下标和最大下标。每次查找时,取 mid \textit{mid} mid low \textit{low} low high \textit{high} high 的平均数向下取整,判断下标 mid \textit{mid} mid 处的数和目标值的大小关系,调整查找的下标范围。

  • 如果 nums [ mid ] = target \textit{nums}[\textit{mid}] = \textit{target} nums[mid]=target,则找到目标值,其下标为 mid \textit{mid} mid

  • 如果 nums [ mid ] > target \textit{nums}[\textit{mid}] > \textit{target} nums[mid]>target,则如果目标值存在,其下标一定小于 mid \textit{mid} mid,因此在下标范围 [ low , mid − 1 ] [\textit{low}, \textit{mid} - 1] [low,mid1] 中继续查找。

  • 如果 nums [ mid ] < target \textit{nums}[\textit{mid}] < \textit{target} nums[mid]<target,则如果目标值存在,其下标一定大于 mid \textit{mid} mid,因此在下标范围 [ mid + 1 , high ] [\textit{mid} + 1, \textit{high}] [mid+1,high] 中继续查找。

如果查找的过程中出现 low > high \textit{low} > \textit{high} low>high,则目标值不存在,插入位置是 low \textit{low} low,返回 low \textit{low} low

每次查找都可以将查找的下标范围减少一半,因此当数组的长度是 n n n 时,二分查找搜索插入位置的时间复杂度是 O ( log ⁡ n ) O(\log n) O(logn)

二分查找搜索插入位置可以使用递归或迭代实现。

解法一

思路和算法

使用递归实现二分查找时,需要在递归调用时指定查找的下标范围。每次查找时,如果当前查找的下标处的元素值等于目标值则返回当前查找的下标,否则根据元素值与目标值的大小关系调整查找的下标范围,然后在新的下标范围中继续查找。

递归调用有以下两个终止条件。

  1. 如果当前的下标范围是空,即 low > high \textit{low} > \textit{high} low>high,则目标值不存在,插入位置是 low \textit{low} low,返回 low \textit{low} low

  2. 如果当前查找的下标处的元素值等于目标值,则返回当前查找的下标。

代码

class Solution {public int searchInsert(int[] nums, int target) {return searchInsert(nums, target, 0, nums.length - 1);}public int searchInsert(int[] nums, int target, int low, int high) {if (low > high) {return low;}int mid = low + (high - low) / 2;if (nums[mid] == target) {return mid;} else if (nums[mid] > target) {return searchInsert(nums, target, low, mid - 1);} else {return searchInsert(nums, target, mid + 1, high);}}
}

复杂度分析

  • 时间复杂度: O ( log ⁡ n ) O(\log n) O(logn),其中 n n n 是数组 nums \textit{nums} nums 的长度。二分查找的次数是 O ( log ⁡ n ) O(\log n) O(logn),每次查找的时间是 O ( 1 ) O(1) O(1),时间复杂度是 O ( log ⁡ n ) O(\log n) O(logn)

  • 空间复杂度: O ( log ⁡ n ) O(\log n) O(logn),其中 n n n 是数组 nums \textit{nums} nums 的长度。空间复杂度主要取决于递归调用栈空间,递归调用栈的层数是 O ( log ⁡ n ) O(\log n) O(logn)

解法二

思路和算法

使用迭代实现二分查找时,需要在二分查找的过程中维护查找的下标范围。每次查找时,如果当前查找的下标处的元素值等于目标值则返回当前查找的下标,否则根据元素值与目标值的大小关系调整查找的下标范围,然后在新的下标范围中继续查找。

查找的过程中,如果当前查找的下标处的元素值等于目标值,则返回当前查找的下标。如果出现 low > high \textit{low} > \textit{high} low>high,则目标值不存在,插入位置是 low \textit{low} low,返回 low \textit{low} low

代码

class Solution {public int searchInsert(int[] nums, int target) {int low = 0, high = nums.length - 1;while (low <= high) {int mid = low + (high - low) / 2;if (nums[mid] == target) {return mid;} else if (nums[mid] > target) {high = mid - 1;} else {low = mid + 1;}}return low;}
}

复杂度分析

  • 时间复杂度: O ( log ⁡ n ) O(\log n) O(logn),其中 n n n 是数组 nums \textit{nums} nums 的长度。二分查找的次数是 O ( log ⁡ n ) O(\log n) O(logn),每次查找的时间是 O ( 1 ) O(1) O(1),时间复杂度是 O ( log ⁡ n ) O(\log n) O(logn)

  • 空间复杂度: O ( 1 ) O(1) O(1)


http://www.mrgr.cn/news/62692.html

相关文章:

  • 【Android】使用TextView实现按钮开关代替Switch开关
  • 点评项目-13-附近商铺、用户签到、UV统计
  • 编程相关学习点——代码内容及结构
  • Android OpenGL ES详解——裁剪Scissor
  • Pycharm报错:Error:failed to find libmagic. Check your installation
  • 107. 阴影范围.shadow.camera
  • 沈阳工业大学《2021年+2020年827自动控制原理真题》 (完整版)
  • Java - 手写识别; 如何用spring ai和大模型做手写识别教程
  • 监控pod日志
  • 集成学习(2)
  • Ethernet 系列(5)-- 物理层测试::PMA Test::MDI
  • 江协科技STM32学习- P28 USART串口数据包
  • 《暗河传》 顺利杀青,苏棋演绎“千面鬼”慕婴引期待
  • 微软办公三件套入局,苹果接力功能再升级!如何进一步提高跨平台协作效率?
  • 【C++】C++17结构化绑定、std::optional、std::variant、std::any
  • Vue全栈开发旅游网项目(3)-Vue路由配置
  • TransUNet 学习记录
  • 淘宝API接口(item_history_price- 淘宝商品历史价格信息查询)
  • idea git 设置Local Changes窗口
  • Python3 No module named ‘pymysql‘
  • SwiftUI(八)- 绑定对象与环境查询
  • vector的模拟实现
  • 【GO学习笔记 go基础】访问控制
  • 局域网实时监控电脑屏幕软件有哪些?8款优秀的局域网监控app!不看巨亏!
  • 使用Kubernetes自动化部署和管理容器化应用
  • 正则表达式(Regular Expressions)