Mind palace

some thoughts

0%

35. Search Insert Position

Posted on Edited on In Disqus:
Symbols count in article: 768 Reading time ≈ 1 mins.

O(logn) time
找lower_bound

1
2
3
4
5
6
7
8
9
10
class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        l, r = 0, len(nums) # 注意直接用左闭右开！！
        while l < r:
            m = l + (r - l) // 2
            if nums[m] < target:
                l = m + 1
            else:
                r = m
        return l
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int n = nums.size();
        int l = 0, r = n; // 直接用左闭右开
        while (l < r) {
            int m = l + (r - l) / 2;
            if (target > nums[m]) {
                l = m + 1;
            } else {
                r = m;
            }
        }
        return l;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int n = nums.size();
        int l = 0, r = n - 1;
        while (l <= r) {
            int m = l + (r - l) / 2;
            if (nums[m] == target) {
                return m;
            } else if (target > nums[m]) {
                l = m + 1;
            } else {
                r = m - 1;
            }
        }
        return l;
    }
};