leetcode-yyc/35.搜索插入位置.py at main · yan-yuchen/leetcode-yyc · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#
# @lc app=leetcode.cn id=35 lang=python3
#
# [35] 搜索插入位置
#

# @lc code=start
class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:

        # 二分查找
        # 二分的核心是找出一个分界点，如果左右两段有不同的性质，二分就能给它找出来
        # 二分查找有两种情况
        l, r = 0, len(nums)-1

        while l < r:
            mid = (l+r)//2
            if nums[mid] >= target:
                r = mid
            else:
                l = mid+1

        # 可能target比所有元素都大
        if nums[r] < target:
            return r+1
        else:
            return r

        # l, r = 0, len(nums)-1

        # while l < r:
        #     mid = (l+r+1)//2
        #     if nums[mid] <= target:
        #         l = mid
        #     else:
        #         r = mid-1

        # if nums[r] < target:
        #     return r+1
        # else:
        #     return r

# @lc code=end