2022-10-09-LeetCodePython-搜索插入位置简单
目录
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 的下标 。二分查找只有一个思想，那就是：逐步缩小搜索区间。
一图解百惑， 上图！
那么，直接 上代码！
# 二分法
class Solution:
def searchInsert(self, nums: List[int], target: int) -> int:
n = len(nums)
left = 0 # 左
right = n - 1 # 右
while left <= right:
mid = (right - left) / 2 + left # 中间
mid = int(mid)
if nums[mid] < target:
left = mid + 1 # 右边从mid+1开始，再次寻找
else:
right = mid - 1 # 左边边从mid+1开始，再次寻找
return left方法二：暴力循环
思路：很简单，暴力循环，设定各种边界条件。直接 上代码！
# if大法
class Solution:
def searchInsert(self, nums: List[int], target: int) -> int:
n = len(nums)
if nums[n - 1] == target: # 最后一位
return n - 1
if nums[n - 1] < target:
return n
if nums[0] > target: # 第一位
return 0
for i in range(n):
if nums[i] == target:
return i
for i in range(n-1):
if nums[i] < target < nums[i + 1]:
return i + 1总结
什么二分查找，边界if大法，中间给我上for循环干它，又不是不能过！
68747470733a2f2f62:6c6f672e6373646e2e6e65742f6d305f36313636313137392f:61727469636c652f64657461696c732f313237323234313137