Find Lower Insertion Point in Python

The problem statement of this tutorial is that if we are given a sorted array of length n and an integer x, then we need to find the lower insertion index of x in the given array. The lower insertion index of any element is the index where we can insert the integer x such that array is still sorted. That means the index of the first element is greater than or equal to x. If x is greater than all the integers of the array, then we will insert it at the nth index, and if it is smaller than all the elements, then we will insert it at the 0 positions.

Sample inputs and Outputs:

Naïve Approach

The simplest solution to this problem would be to run a for loop over the array and find the lower insertion point.

Algorithm:

• Firstly, we will check if the given integer x is less than the first element of the array, then return 0, and if it is greater than the largest element of the matrix, then return n
• We will start a for loop, which will run from 0 to the length of the array - 1.
• Inside the for loop, we will use an if statement. With the help of the if statement, we will check if the current element is equal to or greater than x.
• If the result of the if statement is True, then the function will return the current index. Else it will continue till the last element.

Below is the implementation of the algorithm:

Code

Output:

The element can be inserted at the index:  1

Time Complexity: The time complexity of this program is O(n). Since we are iterating through each array element, it will take O(n) time in the worst-case scenarios.

Space Complexity: O(1). We have not used any extra memory space.

Improved Approach

In this approach, we will use the Binary Search algorithm to find the insertion point.

Algorithm:

• In this approach also, firstly, we will check if the given integer x is less than the first element of the array, then return 0, and if it is greater than the largest element of the matrix, then return n
• We will initialize the variables, low = 0, high = n - 1, and res = 0, and we will store the element's index greater than or equal to x. Then we will start a while loop.
• We will check if the middle element is equal to x then we will store mid in res. Now we have to search for the first occurrence of x in the array. For this case, we have to search the left sub-array.
• If the middle element is smaller than x, we will search for the right sub-array.
• If the middle element is greater than x, we will store the middle index in res and search for the first greater element in the left sub-array.

We will implement this algorithm in Python:

Code

Output:

The element can be inserted at the index:  1 

Time Complexity: The time complexity of this program is O(log n).

We have used a single binary search algorithm; hence the time complexity is O(log n).

Space Complexity: O(1). We have not used any extra memory space.