🦄 Crystal Slot: Binary Search Insert Index

Difficulty: Beginner Tags: binary-search, arrays, search Series: CS 102: Problem Solving & Logic

Problem

Imagine you have a sorted list of numbers and want to add a new number while keeping the list sorted. Where should you put it?

Your task: Given a sorted list and a target number, return the index where the target is found. If it's not in the list, return the index where it should be inserted to keep the list sorted.

Input

data = {
    'nums': list[int],  # Sorted list (ascending order)
    'target': int       # Number to find or insert
}

Output

int  # Index where target is or should be inserted

Constraints

• List length ≤ 100,000
• List is always sorted in ascending order
• Try to solve it in O(log n) time using binary search!

Examples

Example 1: Target Found

Input:  {'nums': [1, 3, 5, 6], 'target': 5}
Output: 2

Why? The number 5 is at index 2 in the list.

Index:  0  1  2  3
List:  [1, 3, 5, 6]
              ↑
          target is here!

Example 2: Target Not Found - Insert in Middle

Input:  {'nums': [1, 3, 5, 6], 'target': 2}
Output: 1

Why? The number 2 isn't in the list, but it should go between 1 and 3.

Before: [1, 3, 5, 6]
After:  [1, 2, 3, 5, 6]  ← 2 inserted at index 1
           ↑

Example 3: Target Larger Than All

Input:  {'nums': [1, 3, 5, 6], 'target': 7}
Output: 4

Why? 7 is bigger than everything, so it goes at the end (index 4).

[1, 3, 5, 6, 7]  ← Insert here (index 4)
             ↑

Example 4: Target Smaller Than All

Input:  {'nums': [1, 3, 5, 6], 'target': 0}
Output: 0

Why? 0 is smaller than everything, so it goes at the beginning (index 0).

[0, 1, 3, 5, 6]  ← Insert here (index 0)
 ↑