Algorithms/LeetCode/SearchInsertPosition.py at master · cyberShaw/Algorithms · 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
class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        def binary(nums, low, high, target):
            if low <= high:
                mid = low + (high - low) // 2
                if nums[mid] == target:
                    return mid
                elif nums[mid] > target:
                    return binary(nums, low, mid-1, target)
                else:
                    return binary(nums, mid+1, high, target)
            else:
                return high+1
        return binary(nums, 0, len(nums)-1, target)

# Iterative Binary Search

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        low = 0
        high = len(nums) - 1
        while low <= high:
            mid = (low + high) // 2
            if nums[mid] == target:
                return mid
            elif nums[mid] > target:
                high = mid - 1
            else:
                low = mid + 1
        else:
            return high + 1