leetcode/python/035_Search_Insert_Position.py at master · terryicoder/leetcode · 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
class Solution:
    # def searchInsert(self, nums, target):
    #     """
    #     :type nums: List[int]
    #     :type target: int
    #     :rtype: int
    #     """
    #     min, pos = 0, 0
    #     max = len(nums) - 1
    #     while min <= max:
    #         # binary search
    #         pos = (max + min) / 2
    #         if nums[pos] == target:
    #             return pos
    #         elif nums[pos] > target:
    #             max = pos - 1
    #         else:
    #             min = pos + 1
    #     if min > pos:
    #         # this means that target is great than pos, and target
    #         # is not in nums
    #         return pos + 1
    #     return pos

    def searchInsert(self, nums, target):
        l, r = 0, len(nums) - 1
        while l < r:
            mid = (l + r) / 2
            if nums[mid] < target:
                l = mid + 1
            else:
                r = mid
        if nums[l] < target:
            return l + 1
        return l