Search Insert Position solution and explanation
Infosys
TCS
Google
IBM
9 more videos on this problem
Search Insert Position - Binary Search - Leetcode 35 - PythonNeetCode · 13:42 · 93K views
Search Insert Position | Leetcode #35Techdose · 7:41 · 60K views
LeetCode 35: Search Insert Position | Binary SearchAbstracted Away · 6:02 · 24K views
Search Insert Position (LeetCode 35) | Full solution with examples animations | Study AlgorithmsNikhil Lohia · 14:52 · 24K views
Search Insert Position | Leetcode 35 | Top 150 interview question seriesTechnosage · 15:30 · 22K views
Search Insert Position - Leetcode 35 - Binary Search (Python)Greg Hogg · 5:58 · 12K views
Leetcode | 35. Search Insert Position | Easy | Java SolutionDeveloper Docs · 5:27 · 9K views
Leetcode 35 Search Insert Position Java Solution | Binary SearchHackerHeap · 6:02 · 5K views
Search Insert Position - LeetCode 35 - JavaScriptAlgoJS · 3:45 · 2K views
LeetCode 35 - Search Insert Position - Java Solution and ExplanationChaz Winter - World Series of AI Games · 13:20 · 956 views
The problem
Given a sorted array of distinct integers and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.
You must write an algorithm with O(log n) runtime complexity.
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
Constraints:
1 <= nums.length <= 104-104 <= nums[i] <= 104numscontains distinct values sorted in ascending order.-104 <= target <= 104
Approach overview
Problem Overview: You are given a sorted array of distinct integers and a target value. Return the index if the target exists. If not, return the index where it should be inserted to maintain sorted order.
Approach 1: Linear Scan (O(n) time, O(1) space)
The simplest idea is to iterate through the array from left to right and stop when you find the first element greater than or equal to the target. That index is either the position of the target or the correct insertion point. If the loop finishes without finding such an element, the target should be inserted at the end of the array. This approach is straightforward but inefficient for large inputs because it may require scanning the entire array.
Approach 2: Iterative Binary Search (O(log n) time, O(1) space)
The array is already sorted, which makes binary search the natural choice. Maintain two pointers left and right representing the current search range. Compute the middle index and compare nums[mid] with the target. If they match, return mid. If the target is larger, move left to mid + 1; otherwise move right to mid - 1. When the loop finishes, left will be the correct insertion position because it points to the first element greater than the target.
Approach 3: Recursive Binary Search (O(log n) time, O(log n) space)
This method applies the same binary search logic but expresses it through recursion. Each recursive call reduces the search range by half based on the comparison with the middle element. When the search interval becomes invalid (left > right), the correct insertion index is simply left. The algorithm still performs logarithmic comparisons, but recursion adds call stack overhead, giving it O(log n) auxiliary space.
Recommended for interviews: Interviewers expect the binary search solution because the array is sorted. Showing the linear scan first demonstrates baseline reasoning, but implementing the iterative binary search proves you recognize the sorted array → logarithmic search optimization. The iterative version is usually preferred over recursion since it avoids extra stack usage while keeping the same O(log n) performance.
Approach 1: Iterative Binary Search
The iterative binary search approach involves using two pointers, 'left' and 'right'. We continue dividing the array into halves until we locate the target or determine where it should be inserted. The algorithm compares the target with the middle element and appropriately adjusts the 'left' or 'right' pointer based on this comparison.
def searchInsert(nums, target):
left, right = 0, len(nums) - 1
while left <= right:
mid = left + (right - left) // 2
if nums[mid] == target:
return mid
elif nums[mid] < target:
left = mid + 1
else:
right = mid - 1
return left
nums = [1, 3, 5, 6]
target = 5
print(searchInsert(nums, target))public class SearchInsertPosition {
public int searchInsert(int[] nums, int target) {
int left = 0, right = nums.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) return mid;
else if (nums[mid] < target) left = mid + 1;
else right = mid - 1;
}
return left;
}
public static void main(String[] args) {
SearchInsertPosition sip = new SearchInsertPosition();
int[] nums = {1, 3, 5, 6};
System.out.println(sip.searchInsert(nums, 5));
}
}#include <iostream>
#include <vector>
using namespace std;
int searchInsert(vector<int>& nums, int target) {
int left = 0, right = nums.size() - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) return mid;
else if (nums[mid] < target) left = mid + 1;
else right = mid - 1;
}
return left;
}
int main() {
vector<int> nums = {1, 3, 5, 6};
int target = 5;
cout << searchInsert(nums, target) << endl;
return 0;
}function searchInsert(nums, target) {
let left = 0;
let right = nums.length - 1;
while (left <= right) {
let mid = Math.floor(left + (right - left) / 2);
if (nums[mid] === target) return mid;
else if (nums[mid] < target) left = mid + 1;
else right = mid - 1;
}
return left;
}
let nums = [1, 3, 5, 6];
let target = 5;
console.log(searchInsert(nums, target));#include <stdio.h>
int searchInsert(int* nums, int numsSize, int target) {
int left = 0, right = numsSize - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) return mid;
else if (nums[mid] < target) left = mid + 1;
else right = mid - 1;
}
return left;
}
int main() {
int nums[] = {1, 3, 5, 6};
int target = 5;
int result = searchInsert(nums, 4, target);
printf("%d\n", result);
return 0;
}using System;
public class Program
{
public static int SearchInsert(int[] nums, int target)
{
int left = 0, right = nums.Length - 1;
while (left <= right)
{
int mid = left + (right - left) / 2;
if (nums[mid] == target) return mid;
else if (nums[mid] < target) left = mid + 1;
else right = mid - 1;
}
return left;
}
public static void Main()
{
int[] nums = {1, 3, 5, 6};
Console.WriteLine(SearchInsert(nums, 5));
}
}The Python solution efficiently finds the index or insert position of the target using binary search technique.
Time Complexity: O(log n)
Space Complexity: O(1)
Approach 2: Recursive Binary Search
In this approach, the binary search is implemented recursively. The function calls itself with updated bounds until the target is found or until it determines the correct insertion index. This approach makes use of stack space due to recursion but is logically intuitive.
def binarySearch(nums, left, right, target):
if left > right:
return left
mid = left + (right - left) // 2
if nums[mid] == target:
return mid
elif nums[mid] < target:
return binarySearch(nums, mid + 1, right, target)
else:
return binarySearch(nums, left, mid - 1, target)
def searchInsert(nums, target):
return binarySearch(nums, 0, len(nums) - 1, target)
nums = [1, 3, 5, 6]
target = 5
print(searchInsert(nums, target))public class SearchInsertPositionRecursive {
public int binarySearch(int[] nums, int left, int right, int target) {
if (left > right) return left;
int mid = left + (right - left) / 2;
if (nums[mid] == target) return mid;
if (nums[mid] < target)
return binarySearch(nums, mid+1, right, target);
else
return binarySearch(nums, left, mid-1, target);
}
public int searchInsert(int[] nums, int target) {
return binarySearch(nums, 0, nums.length - 1, target);
}
public static void main(String[] args) {
SearchInsertPositionRecursive sipr = new SearchInsertPositionRecursive();
int[] nums = {1, 3, 5, 6};
System.out.println(sipr.searchInsert(nums, 5));
}
}#include <iostream>
#include <vector>
using namespace std;
int binarySearch(vector<int>& nums, int left, int right, int target) {
if (left > right) return left;
int mid = left + (right - left) / 2;
if (nums[mid] == target) return mid;
if (nums[mid] < target)
return binarySearch(nums, mid+1, right, target);
else
return binarySearch(nums, left, mid-1, target);
}
int searchInsert(vector<int>& nums, int target) {
return binarySearch(nums, 0, nums.size() - 1, target);
}
int main() {
vector<int> nums = {1, 3, 5, 6};
int target = 5;
cout << searchInsert(nums, target) << endl;
return 0;
}function binarySearch(nums, left, right, target) {
if (left > right) return left;
let mid = Math.floor(left + (right - left) / 2);
if (nums[mid] === target) return mid;
if (nums[mid] < target)
return binarySearch(nums, mid + 1, right, target);
else
return binarySearch(nums, left, mid - 1, target);
}
function searchInsert(nums, target) {
return binarySearch(nums, 0, nums.length - 1, target);
}
let nums = [1, 3, 5, 6];
let target = 5;
console.log(searchInsert(nums, target));#include <stdio.h>
int binarySearch(int* nums, int left, int right, int target) {
if (left > right) return left;
int mid = left + (right - left) / 2;
if (nums[mid] == target) return mid;
if (nums[mid] < target)
return binarySearch(nums, mid+1, right, target);
else
return binarySearch(nums, left, mid-1, target);
}
int searchInsert(int* nums, int numsSize, int target) {
return binarySearch(nums, 0, numsSize - 1, target);
}
int main() {
int nums[] = {1, 3, 5, 6};
int target = 5;
int result = searchInsert(nums, 4, target);
printf("%d\n", result);
return 0;
}using System;
public class Program
{
public static int RecursiveBinarySearch(int[] nums, int left, int right, int target)
{
if (left > right) return left;
int mid = left + (right - left) / 2;
if (nums[mid] == target) return mid;
if (nums[mid] < target)
return RecursiveBinarySearch(nums, mid + 1, right, target);
else
return RecursiveBinarySearch(nums, left, mid - 1, target);
}
public static int SearchInsert(int[] nums, int target)
{
return RecursiveBinarySearch(nums, 0, nums.Length - 1, target);
}
public static void Main()
{
int[] nums = {1, 3, 5, 6};
Console.WriteLine(SearchInsert(nums, 5));
}
}The Python implementation uses recursion within the binary search algorithm to determine the index or insert position.
Time Complexity: O(log n)
Space Complexity: O(log n) due to recursion.
Approach 3: Binary Search
Since the array nums is already sorted, we can use the binary search method to find the insertion position of the target value target.
The time complexity is O(log n), and the space complexity is O(1). Here, n is the length of the array nums.
function searchInsert(nums: number[], target: number): number {
let [l, r] = [0, nums.length];
while (l < r) {
const mid = (l + r) >> 1;
if (nums[mid] >= target) {
r = mid;
} else {
l = mid + 1;
}
}
return l;
}func searchInsert(nums []int, target int) int {
l, r := 0, len(nums)
for l < r {
mid := (l + r) >> 1
if nums[mid] >= target {
r = mid
} else {
l = mid + 1
}
}
return l
}impl Solution {
pub fn search_insert(nums: Vec<i32>, target: i32) -> i32 {
let mut l: usize = 0;
let mut r: usize = nums.len();
while l < r {
let mid = (l + r) >> 1;
if nums[mid] >= target {
r = mid;
} else {
l = mid + 1;
}
}
l as i32
}
}class Solution {
/**
* @param Integer[] $nums
* @param Integer $target
* @return Integer
*/
function searchInsert($nums, $target) {
$l = 0;
$r = count($nums);
while ($l < $r) {
$mid = $l + $r >> 1;
if ($nums[$mid] >= $target) {
$r = $mid;
} else {
$l = $mid + 1;
}
}
return $l;
}
}Approach 4: Binary Search (Built-in Function)
We can also directly use the built-in function for binary search.
The time complexity is O(log n), where n is the length of the array nums. The space complexity is O(1).
func searchInsert(nums []int, target int) int {
return sort.SearchInts(nums, target)
}Complexity comparison
| Approach | Complexity |
|---|---|
| Iterative Binary Search | Time Complexity: O(log n) |
| Recursive Binary Search | Time Complexity: O(log n) |
| Binary Search | – |
| Binary Search (Built-in Function) | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Linear Scan | O(n) | O(1) | Quick baseline solution or when the array size is very small |
| Iterative Binary Search | O(log n) | O(1) | Best choice when the array is sorted and you need optimal performance |
| Recursive Binary Search | O(log n) | O(log n) | Useful for learning recursion or when implementing divide-and-conquer patterns |
Frequently asked questions
Is Search Insert Position easy or hard?
Search Insert Position is classified as an Easy problem on LeetCode. The challenge is recognizing that a sorted array allows binary search instead of scanning the entire array.
Search Insert Position Python/Java solution
In Python or Java, the typical solution uses a while loop with left and right pointers for binary search. Calculate mid, compare nums[mid] with the target, and adjust the search boundaries. When the loop finishes, return left as the insertion position.
How to solve Search Insert Position in O(log n)?
Use binary search with two pointers, left and right. Compare the middle element with the target and shrink the search range accordingly. When the loop ends, the left pointer indicates the correct insertion index, even if the target does not exist in the array.
What is the best approach for Search Insert Position?
Binary search is the best approach because the array is already sorted. It repeatedly halves the search space to find the target or the correct insertion index. This results in O(log n) time complexity and O(1) space when implemented iteratively.
Is Search Insert Position asked at Google/Amazon/Meta?
Search Insert Position is a common introductory binary search problem and frequently appears in interviews at companies like Amazon, Google, and Microsoft. It tests understanding of sorted arrays, boundary conditions, and binary search implementation.
What data structure is used in Search Insert Position?
The problem uses a sorted array as the primary data structure. The algorithm relies on binary search over the array indices to locate the target or determine the correct insertion position efficiently.
What is the time complexity of Search Insert Position?
The optimal binary search solution runs in O(log n) time because each comparison cuts the search range in half. A simple linear scan solution exists with O(n) time, but it is not efficient for large arrays.