Problem No 2
Find the insertion index in a sorted array
Easy≈ 8 minute session
Lesson guide
What this Python exercise practices
Find the insertion index in a sorted array is a beginner practice lesson that focuses on dsa, problem patterns, edge cases. It is designed to be solved in about 8 minutes with examples, starter code, and test feedback.
Prerequisites
- Python functions
- Loops
- Lists
- Basic edge cases
Difficulty and time
- Level
- Beginner
- Estimated time
- 8 minutes
Practice path
Related public exercises
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
Insert into middle
Input
insertion_index([1, 3, 5, 6], 5)
Output
2
Explanation
5 already exists at index 2; insertion index is 2 (leftmost position).
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
Sample input 0
insertion_index([1, 3, 5, 6], 2)
Sample output 0
1
Explanation 0
2 should be inserted between 1 and 3 at index 1.
AI assistant
Ask me anything!
Need help? I can explain the core idea behind this problem, review your current code, and give targeted hints. Use “Teach Theory” for the concept, “Get AI hint” for a quick scaffold nudge, or ask a specific question below.
Chat history is temporary and will not be saved.
Free preview includes 1 Teach Theory response and 1 AI hint per unlocked preview lesson.