/minip.jpg

技术博客分享

2022-10-09-LeetCodePython-搜索插入位置简单

/weixin_miniapp.png

LeetCode(Python)—— 搜索插入位置(简单)

搜索插入位置

概述:给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。请必须使用时间复杂度为 O(log n) 的算法。

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

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

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

方法一:二分查找法

思路:直接套用二分法即可,即不断用二分法逼近查找第一个大于等于 target 的下标 。二分查找只有一个思想,那就是:逐步缩小搜索区间。

一图解百惑, 上图!

https://i-blog.csdnimg.cn/blog_migrate/4df64b8ecd4c0768fd3b9a9aebf5b1fd.gif