Search Insert Position

Difficulty: Easy · Topic: Searching

Given a sorted ascending array of distinct integers and a target, return the index if it is found. If not, return the index where it would be inserted to keep the array sorted.

Examples

search_insert([1,3,5,6], 5)
→ 2

search_insert([1,3,5,6], 2)
→ 1

2 would sit between 1 and 3.

search_insert([1,3,5,6], 7)
→ 4

7 is larger than everything.

Target complexity: time O(log n), space O(1)

Write your solution in Python and run it against hidden tests right on this page. Progressive hints and Python + C++ reference solutions are included.

Learn the idea first: the lesson for this problem.