Search Insert Position Visualization & Animation
Returns the index where a target exists or should be inserted in a sorted array; the lower-bound binary search.
## What is it?
Given a sorted array and a target, return the index where the target would be inserted to maintain sorted order. If the target exists, return its index. This is the "lower bound" operation.
## How it works
- Standard binary search but the result is `low` (not -1) when the target is not found
- If `arr[mid] < target` → move `low = mid + 1`
- If `arr[mid] >= target` → move `high = mid - 1`
- At the end, `low` is the insertion position
## When to use
- Inserting into a sorted array/list while maintaining order
- Finding the leftmost position where a condition becomes true
- Count of elements less than target
## Key Points
- Returns index in range `[0, n]` — n means insert at the very end
- Equivalent to `std::lower_bound` in C++ and `bisect_left` in Python
- The "left boundary" binary search template
Category: algorithms
Difficulty: beginner
Time Complexity: O(log n)
Space Complexity: O(1)
View Search Insert Position Visualization