leetcode with python:35. Search Insert Position

题目:

Given a sorted array of distinct integers and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

You must write an algorithm with O(log n) runtime complexity.

给定一个sorted list跟目标值(target),若target在list内则返回该值的index,若无则返回target放入后阵列还维持sorted list的index值

整个题目二分搜的味道都很重了,题目还将複杂度限制在O(logn),不用二分搜都难

class Solution:    def searchInsert(self, nums: List[int], target: int) -> int:        if target <= nums[0]:  #(1)            return 0                    if target == nums[-1]: #(2)            return len(nums)-1                    if target > nums[-1]:  #(3)            return len(nums)          l=0        r=len(nums)-1        while True:            if target == nums[(l+r)//2]:                return (l+r)//2            if target > nums[(l+r)//2]:                l=(l+r)//2            if target < nums[(l+r)//2]:                r=(l+r)//2                        if l+1==r:                return r

在开始前先处理一些能迅速判断的特例:
(1)target小于第一项那就会insert到第一项的位置,等于第一项就回传第一项的index,两种状况都是回传0
(2)target等于最后一项就回传最后一项的index(len(list)-1)
(3)target大于最后一项会insert到最后一项后,回传最后一项的index+1(len(list))
接着就开始二分,设左值(l)和右值(r),计算左右的中间值(mid),大于mid下限(l)拉高至mid,小于mid上限(r)拉低至mid
一旦侦测到mid和target相等就回传,但若target不在list内,最后l,r会相邻,此时target该插入的index便是r(插入后list仍是sorted list)
最后执行时间47ms(faster than 97.22%)

那我们下题见