Teaching Kids Programming – Insertion Index in Sorted List (bisect_right)

Teaching Kids Programming: Videos on Data Structures and Algorithms

Given a list of integers nums, sorted in ascending order, and a number target, return the index where target should be inserted to keep nums sorted. If target already exists in nums, return the largest index where target can be inserted.

This should be done in O(logn)

Constraints
1 ≤ n ≤ 100,000 where n is the length of nums

Example 1
Input
nums = [1, 2, 4, 5]
target = 3
Output
2

Example 2
Input
nums = [1, 1, 1, 2, 4, 5]
target = 1
Output
3

Example 3
Input
nums = [1]
target = 0
Output
0

Linear Bruteforce Algorithm to Determine the Insertion Index

We can bruteforce, start scanning from the end (largest) until we find the correct index.

1
2
3
4
5
6
7

class Solution:
    def findInsertionIndex(self, nums, target):
        n = len(nums)
        for i in range(n - 1, -1, -1):
            if target >= nums[i]:
                return i + 1
        return 0

class Solution:
    def findInsertionIndex(self, nums, target):
        n = len(nums)
        for i in range(n - 1, -1, -1):
            if target >= nums[i]:
                return i + 1
        return 0

The time complexity is O(N) as in the worst case, we have to scan all the elements and insert the number (smallest) to the array.

Binary Search Algorithm to Find the Index to Insert

As the numbers are sorted, we can binary search to find the correct place for insertion.

1
2
3
4
5
6
7
8
9
10

class Solution:
    def findInsertionIndex(self, nums, target):
        i, j = 0, len(nums) - 1
        while i <= j:
            mid = i + j >> 1
            if target < nums[mid]:
                j = mid - 1
            else:
                i = mid + 1
        return i

class Solution:
    def findInsertionIndex(self, nums, target):
        i, j = 0, len(nums) - 1
        while i <= j:
            mid = i + j >> 1
            if target < nums[mid]:
                j = mid - 1
            else:
                i = mid + 1
        return i

When the target is less than the middle, we continue searching in the lower half, otherwise, we go to the upper half.

The time complexity is O(NLogN).

In Python, we can use the bisect.bisect_right to achieve this:

1
2
3

class Solution:
    def findInsertionIndex(self, nums, target):
        return bisect_right(nums, target)

class Solution:
    def findInsertionIndex(self, nums, target):
        return bisect_right(nums, target)

The bisect_right will return the insertion index for the element in the array to be sorted.

–EOF (The Ultimate Computing & Technology Blog) —