Introduction

The Search Insert Position problem involves finding the index of a target element in a sorted array.

If the target element is not present:

  • return the index where it should be inserted
  • while maintaining sorted order

Given a sorted array arr[] and a target value x, the task is to:

  • return the target index if found
  • otherwise return the correct insertion position

This problem helps in understanding:

  • Binary Search
  • insertion logic
  • sorted array traversal
  • efficient searching techniques

Example

Input: arr[] = [1,3,5,6]x = 5
Output: 2
Explanation:
Element 5 exists at index 2.

Input: arr[] = [1,3,5,6]
x = 2
Output: 1
Explanation:
2 should be inserted at index 1
to maintain sorted order.

Constraints

 1 <= n <= 10^5 -10^9 <= arr[i] <= 10^9 -10^9 <= x <= 10^9  Array is sorted

Approach 1 : Brute Force (Linear Search)

Explanation

The simplest way to solve this problem is:

  1. Traverse the array sequentially
  2. Find the first element:
    • greater than or equal to target
  3. Return its index

This approach works but does not utilize the sorted property efficiently.

Steps

  1. Traverse the array.
  2. Check:
    • arr[i] >= target
  3. If condition becomes true:
    • return index
  4. If traversal completes:
    • return array size

Dry Run

Input Array:[1,3,5,6]
Target = 2

Traverse 1:
1 < 2
Continue traversal

Traverse 3:
3 >= 2
Correct insertion position = 1

Return 1

Brute Force Code

Complexity Analysis

Time Complexity: O(n)Explanation:
Elements are checked sequentially.

Space Complexity: O(1)
Explanation:
No extra data structures are used.

Approach 2 : Optimized Solution (Binary Search)

Explanation

Since the array is sorted, Binary Search can efficiently find:

  • the target index
  • or correct insertion position

The idea is:

  1. Find middle element
  2. Compare middle element with target
  3. Move:
    • left pointer
    • right pointer

If target is not found:

  • left pointer finally represents the correct insertion position

Steps

  1. Initialize:
    • left = 0
    • right = n - 1
  2. While left ≤ right:
    • find middle index
  3. If target found:
    • return middle index
  4. If target greater:
    • move left pointer
  5. Otherwise:
    • move right pointer
  6. Return left pointer.

Dry Run

Input Array:[1,3,5,6]
Target = 2

Initially:
left = 0
right = 3
Middle = 1
arr[1] = 3

3 > 2
Move right pointer
right = 0
Middle = 0
arr[0] = 1

1 < 2
Move left pointer
left = 1
Traversal ends
Correct insert position = 1
Return 1

Optimized Code


Complexity Analysis

Time Complexity: O(log n)Explanation:
Search space is reduced by half in every iteration.

Space Complexity: O(1)
Explanation:
No extra data structures are used.
Edge Cases
  1. Target exists in array
  2. Target smaller than all elements
  3. Target greater than all elements
  4. Array contains one element
  5. Target inserted in middle

Why This Problem is Important

This problem helps in understanding:

  1. Binary Search
  2. Insertion logic
  3. Sorted array optimization
  4. Efficient searching
  5. Pointer manipulation

It is one of the most important searching interview problems.

Real-World Applications

Insertion search concepts are used in:

  1. Database indexing
  2. Sorted collections
  3. Search engines
  4. Ranking systems
  5. Ordered data structures

Common Mistakes

  1. Incorrect pointer updates
  2. Wrong middle calculation
  3. Returning wrong insertion index
  4. Infinite loop conditions

Interview Tips

Interviewers often expect:

  1. O(log n) Binary Search
  2. Correct insertion logic
  3. Proper pointer explanation

Always explain why the left pointer becomes the correct insertion position.

Related Questions

  1. Binary Search
  2. First Occurrence
  3. Last Occurrence
  4. Lower Bound
  5. Upper Bound

Final Takeaway

The Search Insert Position problem is a fundamental Binary Search problem that teaches efficient searching and insertion point calculation techniques. Understanding this problem builds a strong foundation for advanced searching and sorted array interview problems.