Search Insert Position(Sorted Array) lower Bound.

Prerequisites: 🍦Binary Search(Vanilla) , 🔑Find the First True in a Sorted Boolean Array , 🎢Floor (Lower Bound) ,🧩Monotonic function

Question

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

Leetcode

Reframing the Question

1. We have done this question before but we reframed the solution to be the 🛖Ceiling(Upper Bound) in 🎏Search Insert Position(Sorted Array) Upper Bound. In this question, we are going to reform the problem using 🎢Floor (Lower Bound) .
2. Lets us again look over some cases we observed in 🎏Search Insert Position(Sorted Array) Upper Bound.
3. 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 in the array will be shifted to occupy its place.

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

5. Outsiders
1. Targets that are greater than 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

1. We can do it in linear search, scan all the elements starting from index 0, and return the element before we reach anything greater than the target or the element itself if it exists. Since the array is sorted, can we do it in logarithmic time?
2. Divide the array into two halves: the upper half contain all values greater than the target(place to insert); the target will be to the left, and the lower half (True) containing all values less than and equal to the target; the place to insert will be to the right.
3. Seems simple enough not really reframing to 🎢Floor (Lower Bound) . But will leave us some headaches in dealing with edge cases.
4. We can't simply return the last value in the lower half(True). Why?
5. The lower half (true), has all values less than the target (the place where the value needs to be inserted). If the target is not in the array, the place where the target will be inserted is right after the largest element before it, not on it. That's why we have to return Floor + 1 as the insertion point.(complicated in know)


6. Dealing with outsiders will be different, less than nums[0]
1. We are looking for the largest element before or equal to the target. In this case, there are no candidates that meet this criterion. If no elements before the target found we will insert it at index 0

2. We don't have to worry about that when the value is greater than nums[-1], as that will be covered in the statement for the floor plus one.

7. The last thing to consider is when our value is the same as the target. We will return an index one off from where the targets are equal.

Implementation

class Solution:

    def floor(self, nums,target):

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

        while left <= right:

            mid = left + (right - left) // 2

            #True
                # Possible Value

            if nums[mid] >= target :
                floor = mid
                left = mid + 1

						# False
            else: # target < nums[mid]:
                right = mid - 1
        # if not found will return -1  
        return floor

class Solution:

    def searchInsert(self, nums,target):

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

        while left <= right:

            mid = left + (right - left) // 2

            #True
                # Possible Value

            if nums[mid] <= target :
                floor = mid
                left = mid + 1

            # False
            else: # target < nums[mid]:
                right = mid - 1

                
        # if not found will return the first index
        if floor == -1:
            return 0 
        # if equal to the target return floor
        if nums[floor] == target:
            return floor
        else:
            return floor + 1

SandBox PythonTutor (Visualized)

Take away

In the Takeaway section for 🎢Floor (Lower Bound) we talked about how 🎢Floor (Lower Bound) and 🛖Ceiling(Upper Bound) ) are frameworks to reframe complex problems into simpler challenges. Until now we have solved the same problem with both of these frameworks.🎏Search Insert Position(Sorted Array) Upper Bound and Search Insert Position(Sorted Array) lower Bound. This problem was way easier to solve with the Upper bound rather than the lower bound as we had to deal with many edge cases. The takeaway from this question should be that some problems are easier to solve with one or the other framework, the choice is yours.

Complexities

Time Complexity: O(log(n))

Space Complexity: O(1)

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