Leetcode 0035. Search Insert Position

https://leetcode.com/problems/search-insert-position

Solution 1: bisect

It is not said in the problem statement not to use any libraries, so why not use bisect_left function, so conviniently provided by python? Why we use bisect_left? Because for [1,3,5,6] and number 5 we need to return index 2: if element is already present in array, the insertion point will be before (to the left of) any existing entries.

Complexity is classical for binary search: O(log n)

class Solution:
    def searchInsert(self, nums, target):
        return bisect.bisect_left(nums, target)

Solution 2: Classical binary search

Classical binary search problem, where we need to return beg in the end, because we are looking for left place to insert our symbol.

class Solution:
    def searchInsert(self, nums, target):
        beg, end = 0, len(nums)
        while beg < end:
            mid = (beg + end)//2
            if nums[mid] >= target:
                end = mid
            else:
                beg = mid + 1
        return beg

If you like the solution, you can upvote it on leetcode discussion section: Problem 0035