Search Insert Position - Java Coding Interview Guide
Learn how to solve the Search Insert Position problem using Binary Search in Java with explanation, algorithm, dry run, complexity analysis, production use cases, common mistakes, and interview questions.
Search Insert Position
Java Coding Interview Track
Binary Search — Lesson 02
Ordered Lessons
| # | Lesson |
|---|---|
| 01 | Binary Search |
| 02 | Search Insert Position ← |
| 03 | First Last Position |
| 04 | Find Peak Element |
| 05 | Search Rotated Array |
| 06 | Binary Search Interview |
Problem Statement
Given a sorted array of distinct integers and a target value:
- Return the index if the target exists.
- Otherwise, return the index where it should be inserted to maintain the sorted order.
This problem is one of the most common Binary Search interview questions and appears frequently in coding interviews.
Example 1
Input
nums = [1,3,5,6]
target = 5
Output
2
Example 2
Input
nums = [1,3,5,6]
target = 2
Output
1
Example 3
Input
nums = [1,3,5,6]
target = 7
Output
4
Example 4
Input
nums = [1,3,5,6]
target = 0
Output
0
Understanding the Problem
Consider:
1 3 5 6
Target = 4
4 doesn't exist.
Where should it be inserted?
1 3 4 5 6
↑
Answer = Index 2
Instead of inserting the value, we only return the position.
Brute Force Solution
Traverse the array.
Return the first index where
nums[i] >= target
Otherwise return
nums.length
Complexity
Time
O(n)
Space
O(1)
Optimal Solution
Since the array is already sorted,
Binary Search can solve this in
O(log n)
The idea:
- Search normally.
- If target exists, return its index.
- If not found, the left pointer indicates the insertion position.
Algorithm
left = 0
right = n-1
while(left <= right)
mid
if found
return mid
if target < nums[mid]
right = mid-1
else
left = mid+1
Return left
Dry Run
nums
1 3 5 6
target = 2
Iteration 1
left = 0
right = 3
mid = 1
nums[mid] = 3
Move left
right = 0
Iteration 2
left = 0
right = 0
mid = 0
nums[mid] = 1
Move right
left = 1
Loop ends
left = 1
Answer = 1
Java Solution
public class SearchInsertPosition {
public static int searchInsert(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
return mid;
}
if (target < nums[mid]) {
right = mid - 1;
} else {
left = mid + 1;
}
}
return left;
}
public static void main(String[] args) {
int[] nums = {1,3,5,6};
System.out.println(searchInsert(nums,2));
}
}
Complexity Analysis
| Operation | Complexity |
|---|---|
| Time | O(log n) |
| Space | O(1) |
Why Return Left?
When Binary Search finishes:
left > right
The left pointer always points to the correct insertion position.
Example
1 3 5 6
Target = 4
Final state
left = 2
right = 1
Insert at index
2
Visualization
Array
1 3 5 6
Target = 4
↓
Discard Left
↓
Discard Right
↓
left = 2
↓
Insert Here
Production Use Cases
Leaderboards
Find where a new score should be inserted.
Student Ranking
Insert a student's rank while keeping the ranking sorted.
Product Pricing
Insert products into sorted price lists.
Calendar Events
Find the correct position for a new appointment.
Search Suggestions
Maintain alphabetically sorted suggestions.
Database Indexes
Find insertion location inside sorted indexes.
Common Mistakes
Returning right
Wrong
return right;
Correct
return left;
Wrong loop
Wrong
while(left < right)
Correct
while(left <= right)
Overflow
Wrong
int mid = (left + right) / 2;
Correct
int mid = left + (right-left)/2;
Interview Tips
Always mention:
- Array is sorted.
- Binary Search reduces search space by half.
- Left pointer becomes insertion index.
- Complexity is O(log n).
Related Problems
- Binary Search
- Lower Bound
- Upper Bound
- First Occurrence
- Last Occurrence
- Floor and Ceil
- Search Range
- Search in Rotated Array
Interview Questions
1. Why is Binary Search suitable for this problem?
Answer
Because the input array is sorted, allowing us to eliminate half of the search space in each iteration.
2. Why do we return left instead of right?
Answer
After the loop ends, left points to the smallest index where the target can be inserted while maintaining sorted order.
3. What is the time complexity?
Answer
O(log n) because the search space is halved in every iteration.
4. What is the space complexity?
Answer
O(1) for the iterative solution.
5. Can duplicates affect this solution?
Answer
This problem assumes distinct elements. With duplicates, variants like Lower Bound or First Occurrence are typically used.
6. Why use left + (right - left) / 2?
Answer
It prevents integer overflow that can occur with (left + right) / 2.
7. What happens if the target is larger than every element?
Answer
The algorithm returns nums.length, indicating the target should be inserted at the end.
8. What happens if the target is smaller than every element?
Answer
The algorithm returns 0, meaning the target should be inserted at the beginning.
9. Can this approach be implemented recursively?
Answer
Yes, but the iterative approach is preferred because it avoids recursive stack overhead.
10. Where is this concept used in real systems?
Answer
Leaderboards, search engines, database indexes, calendars, product catalogs, ranking systems, and sorted collections.
Quick Revision
| Concept | Value |
|---|---|
| Pattern | Binary Search |
| Input | Sorted Array |
| Return | Existing Index / Insert Position |
| Time Complexity | O(log n) |
| Space Complexity | O(1) |
| Key Observation | Return left |
| Interview Frequency | ⭐⭐⭐⭐⭐ |
Key Takeaways
- Search Insert Position is a classic Binary Search interview problem.
- If the target exists, return its index.
- Otherwise, return the position where it should be inserted.
- The
leftpointer represents the insertion point after the search completes. - Mastering this problem helps solve advanced Binary Search problems such as Lower Bound, Upper Bound, First/Last Occurrence, and Search Range.