Find the insertion index in a sorted array

Summary

Find the index where a target should be inserted into a sorted list to keep it sorted (leftmost position).

Problem statement

Given a sorted list of integers in ascending order and a target integer, return the index at which the target should be inserted to maintain sorted order. If the target already exists, return the index of the first element that is >= target (i.e., insert to the left of equal elements). Implement this using a binary search approach with O(log n) time complexity.

Task

Implement insertion_index(arr, target) returning the leftmost index to insert target in sorted arr.

Examples

Input format

A sorted list of integers 'arr' and an integer 'target' passed to insertion_index(arr, target).

Output format

An integer index (0-based) where target should be inserted.

Constraints

0 <= len(arr) <= 10^5. Time complexity O(log n).

Samples