🎏

Search Insert Position(Sorted Array) Upper Bound

Prerequsites : 🍦Binary Search(Vanilla) , 🔑Find the First True in a Sorted Boolean Array , 🛖Ceiling(Upper Bound)

Question

Given a sorted array of distinct integers and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

You must write an algorithm with O(log n) runtime complexity.

Input: nums = [1,3,5,6], target = 5
Output: 2

Leetcode

Reframing the Question

Let's look at some cases to clarify.

If the target value to be inserted lies between the range of numbers from nums[0] (the first) to nums[-1] (the last), any number greater than the target will be shifted to occupy its place.

If a number in the array is equal to the target (value to be inserted), the same number will be pushed.

Outsiders

Targets that are greater than values at nums[-1] will be inserted at the very end of the sorted array as a new index.

b. Targets that are less than the first element nums[0] will shift any number greater than it so that it occupies its place.

Intuition

We can use linear search to traverse the array until we find the first element that is greater than or equal to the target. The index of this element is the answer we should return. If no such element is found, we should return the last index plus one (which will be the length of the array, accounting for indexes being 0-based). Since the array is sorted, can we perform this search in logarithmic time?

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        for i in range(len(nums)):
            if nums[i] >= target:
                return i
        return len(nums)

Divide the array into two halves: the upper half containing all values greater than or equal to the target, and the lower half containing all values less than the target.
It will turn out that the place where we need to insert the element will be the first element in the upper half which is the smallest element after the target (and including).

If the value to be inserted is equal to a value in the array, it will be placed as the first element in the upper half. (5 replacing 5)

If the value to be inserted is not equal to any value in the array, it will be inserted at the first element that is greater than itself in the array. This will also happen to be the first element in the upper half. (2 replacing 3)

Reducing the problem to finding the 🛖Ceiling(Upper Bound).

Code for ceil

class Solution:

    def ceil(self,nums,target):

        left, right = 0, len(nums) - 1
        ceil = -1

        while left <= right:

            mid = left + (right - left) // 2
						
            #True
                # Possible Value
            if nums[mid] >= target:
                ceil = mid
                right = mid - 1
						
						# False
            else: # target > nums[mid]
                left = mid + 1

				# if not found will return -1  
        return ceil

Code for this Question with changes

class Solution:

    def searchInsert(self, nums,target):

        left, right = 0, len(nums) - 1
        ceil = -1

        while left <= right:

            mid = left + (right - left) // 2
						
            #True
                # Possible Value
            if nums[mid] >= target:
                ceil = mid
                right = mid - 1
						
		    # False
            else: # target > nums[mid]
                left = mid + 1

        # if not found will return len(nums) as it is the one off the last index
        return len(nums) if ceil == -1 else ceil

SandBox PythonTutor (Visualized)

Complexities

Time Complexity: O(log(n))

Space Complexity: O(1)

📐Understanding Time Complexity of OLog(N): Math + Intuition