What happens if you using mid = (left + right) / 2 without floor or integer division?

In some languages, this causes float index or wrong mid calculation Fix: Use integer division or floor function to get integer mid

What happens if you not updating left or right pointers correctly (off-by-one errors)?

Infinite loop or incorrect insertion index Fix: Ensure left = mid + 1 or right = mid - 1 depending on comparison

What happens if you returning right instead of left after loop ends?

Wrong insertion index returned Fix: Return left pointer as insertion position after loop

What happens if you not handling empty array input?

Code may crash or return invalid index Fix: Check if array is empty and return 0 as insertion position

Interview Prepmodified-binary-searcheasyAmazonGoogle

Search Insert Position

Choose your preparation mode4 modes available

Try It Solution Trace

🎯

easyBINARY_SEARCHAmazonGoogle

Imagine you have a sorted list of book titles and want to find where to insert a new title so the list remains sorted.

💡 This problem is about finding the correct position to insert a target value in a sorted array. Beginners often struggle because they try linear search or don't understand how binary search can be adapted to find insertion points, not just exact matches.

📋

Problem Statement

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.

1 ≤ nums.length ≤ 10^5-10^4 ≤ nums[i], target ≤ 10^4nums contains distinct values sorted in ascending order

💡

Example

Input"nums = [1,3,5,6], target = 5"

Output2

Target 5 is found at index 2.

Input"nums = [1,3,5,6], target = 2"

Output1

Target 2 is not found; it would be inserted at index 1 to keep array sorted.

Input"nums = [1,3,5,6], target = 7"

Output4

Target 7 is greater than all elements, so insert at the end (index 4).

Input"nums = [1,3,5,6], target = 0"

Output0

Target 0 is smaller than all elements, so insert at the beginning (index 0).

Single element array, target less than element → insert at 0
Single element array, target greater than element → insert at 1
Target equals first element → return 0
Target equals last element → return last index

⚠️

Common Mistakes

Using mid = (left + right) / 2 without floor or integer division

In some languages, this causes float index or wrong mid calculation

✅ Use integer division or floor function to get integer mid

Not updating left or right pointers correctly (off-by-one errors)

Infinite loop or incorrect insertion index

✅ Ensure left = mid + 1 or right = mid - 1 depending on comparison

Returning right instead of left after loop ends

Wrong insertion index returned

✅ Return left pointer as insertion position after loop

Not handling empty array input

Code may crash or return invalid index

✅ Check if array is empty and return 0 as insertion position

Using linear search in large arrays during interview

Inefficient solution leading to time limit exceeded

✅ Use binary search to achieve O(log n) time

🧠

Brute Force (Linear Search)

💡 This approach exists to build intuition by checking each element one by one. It is simple but inefficient for large arrays, highlighting why binary search is needed.

Intuition

Scan the array from left to right and find the first element greater than or equal to the target. The index of this element is the insertion position.

Algorithm

Start from the first element and iterate through the array.
For each element, check if it is greater than or equal to the target.
If yes, return the current index as the insertion position.
If no element is greater or equal, return the length of the array.

💡 The algorithm is straightforward but inefficient because it checks every element even if the array is sorted.

</>

Code

def searchInsert(nums, target):
    for i in range(len(nums)):
        if nums[i] >= target:
            return i
    return len(nums)

# Driver code
if __name__ == '__main__':
    print(searchInsert([1,3,5,6], 5))  # Output: 2
    print(searchInsert([1,3,5,6], 2))  # Output: 1
    print(searchInsert([1,3,5,6], 7))  # Output: 4
    print(searchInsert([1,3,5,6], 0))  # Output: 0

Line Notes

for i in range(len(nums))Iterate over each index to check elements sequentially

if nums[i] >= targetCheck if current element is the insertion point or exact match

return iReturn index immediately when insertion point found

return len(nums)If no element is greater or equal, insert at the end

public class Solution {
    public static int searchInsert(int[] nums, int target) {
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] >= target) {
                return i;
            }
        }
        return nums.length;
    }

    public static void main(String[] args) {
        System.out.println(searchInsert(new int[]{1,3,5,6}, 5)); // 2
        System.out.println(searchInsert(new int[]{1,3,5,6}, 2)); // 1
        System.out.println(searchInsert(new int[]{1,3,5,6}, 7)); // 4
        System.out.println(searchInsert(new int[]{1,3,5,6}, 0)); // 0
    }
}

Line Notes

for (int i = 0; i < nums.length; i++)Loop through array elements sequentially

if (nums[i] >= target)Check if current element is suitable insertion point

return i;Return index immediately when condition met

return nums.length;Insert at end if no element is greater or equal

#include <iostream>
#include <vector>
using namespace std;

int searchInsert(vector<int>& nums, int target) {
    for (int i = 0; i < nums.size(); i++) {
        if (nums[i] >= target) {
            return i;
        }
    }
    return nums.size();
}

int main() {
    vector<int> nums1 = {1,3,5,6};
    cout << searchInsert(nums1, 5) << endl; // 2
    cout << searchInsert(nums1, 2) << endl; // 1
    cout << searchInsert(nums1, 7) << endl; // 4
    cout << searchInsert(nums1, 0) << endl; // 0
    return 0;
}

Line Notes

for (int i = 0; i < nums.size(); i++)Sequentially check each element in vector

if (nums[i] >= target)Find first element not less than target

return i;Return insertion index immediately

return nums.size();If none found, insert at end

function searchInsert(nums, target) {
    for (let i = 0; i < nums.length; i++) {
        if (nums[i] >= target) {
            return i;
        }
    }
    return nums.length;
}

// Test cases
console.log(searchInsert([1,3,5,6], 5)); // 2
console.log(searchInsert([1,3,5,6], 2)); // 1
console.log(searchInsert([1,3,5,6], 7)); // 4
console.log(searchInsert([1,3,5,6], 0)); // 0

Line Notes

for (let i = 0; i < nums.length; i++)Loop through array elements one by one

if (nums[i] >= target)Check if current element is insertion point

return i;Return index immediately when found

return nums.length;Insert at end if no suitable element found

⏱

Complexity

TimeO(n)

SpaceO(1)

We scan the array once until we find the insertion point or reach the end, so time is linear in array size.

💡 For n=100, this means up to 100 comparisons, which is inefficient for large arrays.

Interview Verdict: Accepted but inefficient for large inputs

This approach works but is too slow for large arrays, motivating binary search.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force (Linear Search)	`O(n)`	`O(1)`	No	N/A	Mention only - never code for large inputs
2. Binary Search (Iterative)	`O(log n)`	`O(1)`	No	N/A	Code this approach in interviews
3. Binary Search (Recursive)	`O(log n)`	`O(log n)`	Yes (deep recursion)	N/A	Mention or code if interviewer requests recursion

Practice

(1/5)

1. You are given an n x n matrix where each row and each column is sorted in ascending order. You need to find the kth smallest element in the matrix efficiently. Which of the following approaches guarantees the optimal time complexity for this problem?

easy

A. Use a greedy approach by repeatedly picking the smallest element from the matrix without extra data structures.

B. Flatten the matrix into a list, sort it, and return the kth element.

C. Apply dynamic programming to build a table of smallest elements up to k.

D. Use a min-heap to merge the sorted rows, extracting the smallest elements until the kth is found.

3. Consider the following buggy code for the Koko Eating Bananas problem. Which line contains the subtle bug that can cause incorrect results on some inputs?

from math import ceil

def can_finish(piles, speed, h):
    hours = 0
    for pile in piles:
        hours += pile // speed  # Line 6
        if hours > h:
            return false
    return true

def minEatingSpeed(piles, h):
    low, high = 1, max(piles)
    while low < high:
        mid = (low + high) // 2
        if can_finish(piles, mid, h):
            high = mid
        else:
            low = mid + 1
    return low

medium

A. Line 9: Returning true when hours <= h

B. Line 3: import statement

C. Line 6: Using floor division instead of ceiling division

D. Line 14: Updating low to mid + 1

Recommended

Ready to prove it?

Pass the test and this pattern moves unknown strong while earning +1 Grip toward your certificate.

10 questions~5 mineasy hard

Intuition

Algorithm

Intuition

Algorithm

Intuition

Algorithm

How to Present

Time Allocation

What the Interviewer Tests

Common Follow-ups

When to Use

Signature Phrases

NOT This Pattern When

Similar Problems

Practice

Solution

Step 1: Understand problem constraints

Step 2: Identify the optimal approach

Final Answer:

Quick Check:

Solution

Step 1: Identify the purpose of is_feasible

Step 2: Spot the bug in division

Step 3: Consequence of the bug

Final Answer:

Quick Check:

Solution

Step 1: Identify how hours are calculated

Step 2: Understand impact on feasibility

Final Answer:

Quick Check:

Solution

Step 1: Identify outer binary search on answer space

Step 2: Analyze feasibility check using binary search on prefix sums

Final Answer:

Quick Check:

Solution

Step 1: Understand duplicates impact

Step 2: Modify pivot search

Step 3: Complexity consideration

Final Answer:

Quick Check:

Ready to prove it?