一、前记(3/3)

今天完成了本周的算法任务,这样一路一路的坚持下来还挺不容易的,希望自己能坚持下来。这周学习到了两个非常重要的算法:第一个就是上次见到的非常有意思的KMP算法(会单独拿出来专门写一篇blog)。一个就是今天学习到的二分法。其实第一次见到二分法应该是在大一的时候,但是都已经记不得了,今天这个题目刚好可以使用二分法进行解决。

二、题目描述

三、解题思路

1、我的思路

我的思路特别的常规。因为给的数组是一个顺序数组(从小到大),就按照顺序进行比较。当target<=nums[i]的时候就找到了适合target的索引值,返回i的值就可以。但是在这里一定要注意一点,在原数组的末尾一定要添加一个无穷大的数(append(float("inf"))),这样子避免target的数值大于数组里面的所有数值而导致无法返回正确的索引值。

参考代码:

#encoding:utf-8
class Solution:
    def searchInsert(self, nums, target: int) -> int:
        i=0
        nums.append(float('inf'))
        for i in range(len(nums)):
            if target <= nums[i]:
                return i

#as a checking
solution=Solution()
a=[1,3,5,6]
b=0
print(solution.searchInsert(a,b))

2、别人的思路

其实别人的思路就是二分法。二分法我感觉比较值得注意的就是,注意范围的扩大和缩小,因为在不断的二分,所以范围肯定要有所变化。

参考代码:

#encoding:utf-8
class Solution:
    def searchInsert(self, nums, target: int) -> int:
        if target>nums[len(nums)-1]:
            return len(nums)
        i=0
        r=len(nums)-1   #索引
        while i<r:
            m=(i+r)//2
            if target > nums[m]:    #在后半段,更改i,改为后半段范围
                i=m+1
            else:
                r=m     #在前半段,更改r,改为前半段范围
        return i    #最终i>r得到结果


#as a checking
solution=Solution()
a=[1,3,5,6]
b=0
print(solution.searchInsert(a,b))

四、学到了什么?

(1)python无穷大和无穷小的表达方式

(2)二分查找算法