What happens if you using mid = (low + high) / 2 without overflow protection?

Integer overflow on large arrays causing wrong mid calculation Fix: Use mid = low + (high - low) // 2 to avoid overflow

What happens if you using while (low < high) instead of while (low <= high)?

May miss checking the last element, causing incorrect -1 return Fix: Use while (low <= high) to ensure all elements are checked

What happens if you updating low = mid instead of low = mid + 1?

Infinite loop when low equals mid repeatedly Fix: Increment low to mid + 1 to shrink search space

What happens if you not handling empty array input?

Index errors or incorrect output Fix: Check if array is empty before searching or handle gracefully

Interview Prepmodified-binary-searcheasyAmazonGoogleFacebookMicrosoft

Binary Search

Choose your preparation mode4 modes available

Try It Solution Trace

🎯

Binary Search

easyBINARY_SEARCHAmazonGoogleFacebook

Imagine searching for a specific book in a sorted library shelf. Instead of checking every book, you cleverly split the shelf in half repeatedly to find your book faster.

💡 Binary Search is a fundamental algorithm used to efficiently find an element in a sorted array. Beginners often struggle with correctly managing the search boundaries and termination conditions, which can lead to infinite loops or missed elements.

📋

Problem Statement

Given a sorted array of integers nums and an integer target, return the index of target if it exists in nums. Otherwise, return -1. You must write an algorithm with O(log n) runtime complexity.

1 ≤ nums.length ≤ 10^5-10^9 ≤ nums[i], target ≤ 10^9nums is sorted in ascending order

💡

Example

Input"nums = [-1,0,3,5,9,12], target = 9"

Output4

9 is found at index 4 in the array.

Input"nums = [-1,0,3,5,9,12], target = 2"

Output-1

2 is not present in the array, so return -1.

Empty array → return -1
Target smaller than all elements → return -1
Target larger than all elements → return -1
Array with one element equal to target → return 0

⚠️

Common Mistakes

Using mid = (low + high) / 2 without overflow protection

Integer overflow on large arrays causing wrong mid calculation

✅ Use mid = low + (high - low) // 2 to avoid overflow

Using while (low < high) instead of while (low <= high)

May miss checking the last element, causing incorrect -1 return

✅ Use while (low <= high) to ensure all elements are checked

Updating low = mid instead of low = mid + 1

Infinite loop when low equals mid repeatedly

✅ Increment low to mid + 1 to shrink search space

Not handling empty array input

Index errors or incorrect output

✅ Check if array is empty before searching or handle gracefully

🧠

Brute Force (Linear Search)

💡 This approach exists to establish a baseline solution that is easy to understand but inefficient. It helps beginners grasp the problem before optimizing.

Intuition

Check each element one by one until the target is found or the array ends.

Algorithm

Start from the first element of the array.
Compare the current element with the target.
If they match, return the current index.
If the end of the array is reached without a match, return -1.

💡 This algorithm is straightforward but inefficient for large arrays because it checks every element.

</>

Code

def linear_search(nums, target):
    for i in range(len(nums)):
        if nums[i] == target:
            return i
    return -1

# Driver code
if __name__ == '__main__':
    nums = [-1,0,3,5,9,12]
    target = 9
    print(linear_search(nums, target))  # Output: 4

Line Notes

for i in range(len(nums))Iterate over each index to check every element

if nums[i] == targetCheck if current element matches the target

return iReturn index immediately upon finding the target

return -1Return -1 if target is not found after full scan

public class LinearSearch {
    public static int linearSearch(int[] nums, int target) {
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == target) {
                return i;
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        int[] nums = {-1,0,3,5,9,12};
        int target = 9;
        System.out.println(linearSearch(nums, target)); // Output: 4
    }
}

Line Notes

for (int i = 0; i < nums.length; i++)Loop through each element in the array

if (nums[i] == target)Check if current element equals target

return iReturn index when target is found

return -1Return -1 if target is not found after loop

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

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

int main() {
    vector<int> nums = {-1,0,3,5,9,12};
    int target = 9;
    cout << linearSearch(nums, target) << endl; // Output: 4
    return 0;
}

Line Notes

for (int i = 0; i < nums.size(); i++)Iterate over all elements in the vector

if (nums[i] == target)Check if current element matches target

return iReturn index immediately when found

return -1Return -1 if target not found after full iteration

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

// Driver code
const nums = [-1,0,3,5,9,12];
const target = 9;
console.log(linearSearch(nums, target)); // Output: 4

Line Notes

for (let i = 0; i < nums.length; i++)Loop through each element in the array

if (nums[i] === target)Check if current element equals target

return iReturn index immediately when target is found

return -1Return -1 if target is not found after full loop

⏱

Complexity

TimeO(n)

SpaceO(1)

We potentially check every element once, so time is linear in array size. Space is constant as no extra storage is used.

💡 For n=100, this means up to 100 comparisons, which is inefficient compared to binary search.

Interview Verdict: Accepted but inefficient for large inputs

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

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	`O(n)`	`O(1)`	No	N/A	Mention only - never code
2. Binary Search Iterative	`O(log n)`	`O(1)`	No	N/A	Code this approach
3. Binary Search Recursive	`O(log n)`	`O(log n)`	Yes (deep recursion)	N/A	Mention as alternative, rarely code

Practice

(1/5)

1. Consider the following Python function that finds the kth positive missing number from a sorted array arr. What is the returned value when calling findKthPositive([2, 4, 7], 3)?

def findKthPositive(arr, k):
    n = len(arr)
    total_missing = arr[-1] - n
    if k > total_missing:
        return arr[-1] + (k - total_missing)
    left, right = 0, n - 1
    while left <= right:
        mid = (left + right) // 2
        missing = arr[mid] - (mid + 1)
        if missing < k:
            left = mid + 1
        else:
            right = mid - 1
    return arr[right] + (k - (arr[right] - (right + 1)))

easy

A. 5

B. 8

C. 9

D. 7

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: Calculate total missing numbers

Step 2: Perform binary search iterations

Final Answer:

Quick Check:

Solution

Step 1: Understand problem constraints

Step 2: Identify the optimal approach

Final Answer:

Quick Check:

Solution

Step 1: Calculate prefix sums

Step 2: Binary search on answer space [7,24]

Final Answer:

Quick Check:

Solution

Step 1: Understand the relaxed constraint

Step 2: Identify correct approach

Step 3: Why other options fail

Final Answer:

Quick Check:

Solution

Step 1: Understand reuse of elements

Step 2: Identify suitable approach

Step 3: Why other options fail

Final Answer:

Quick Check:

Ready to prove it?