Binary Search

📋

Binary Search

Edge cases:

</>

IDE

def binary_search(nums: list[int], target: int) -> int:public int binary_search(int[] nums, int target)int binary_search(vector<int> nums, int target)function binary_search(nums, target)

def binary_search(nums, target):
    # Write your solution here
    pass

class Solution {
    public int binary_search(int[] nums, int target) {
        // Write your solution here
        return -1;
    }
}

#include <vector>
using namespace std;

int binary_search(vector<int> nums, int target) {
    // Write your solution here
    return -1;
}

function binary_search(nums, target) {
    // Write your solution here
    return -1;
}

Common Bugs to Avoid

Wrong: -1 when target existsIncorrect loop condition or mid calculation causing search to miss target.✅ Use while low <= high and mid = low + (high - low) // 2; update low = mid+1 if nums[mid]<target else high = mid-1.

Wrong: Index out of range or infinite loopOff-by-one error in updating low or high pointers.✅ Ensure low and high are updated correctly without skipping valid indices; use mid calculation to avoid overflow.

Wrong: Crashes or wrong output on empty arrayNo check for empty input before binary search.✅ Add condition to return -1 if nums is empty before starting search.

Wrong: TLE on large inputUsing linear search instead of binary search.✅ Implement binary search with O(log n) complexity.

✓

Test Cases

Focus on handling empty and minimal input arrays correctly.

Check your boundary conditions and mid calculations carefully.

Optimize your solution to run in logarithmic time for large inputs.

t1_01basic

Input{"nums":[-1,0,3,5,9,12],"target":9}

Expected4

⏱ Performance - must finish in 2000ms

9 is found at index 4 in the array.

💡 Binary search splits the array to find the target efficiently.

💡 Check mid = (low + high) // 2 and compare nums[mid] with target.

💡 Return mid if nums[mid] == target; else adjust low or high accordingly.

Why it failed: Returned wrong index or -1 despite target present. Likely mid calculation or update of low/high incorrect. Fix: ensure mid = (low + high) // 2 and update low = mid+1 if nums[mid]<target, else high = mid-1.

✓ Correct index returned using classic binary search.

t1_02basic

Input{"nums":[1,2,4,6,8,10,12],"target":6}

Expected3

⏱ Performance - must finish in 2000ms

6 is found at index 3 in the array.

💡 Binary search halves the search space each step.

💡 Check mid element and adjust search boundaries accordingly.

💡 Return mid index when nums[mid] equals target.

Why it failed: Incorrect index or -1 returned though target exists. Possibly off-by-one error in updating low/high pointers. Fix: update low = mid+1 when nums[mid]<target, high = mid-1 when nums[mid]>target.

✓ Binary search correctly locates the target index.

t2_01edge

Input{"nums":[],"target":5}

Expected-1

⏱ Performance - must finish in 2000ms

Empty array always returns -1 as target cannot be found.

💡 Check if array is empty before searching.

💡 If nums length is zero, return -1 immediately.

💡 Add a base case to handle empty input arrays.

Why it failed: Code crashes or returns wrong index on empty array. Fix: add condition to return -1 if nums is empty before binary search.

✓ Correctly returns -1 for empty input.

t2_02edge

Input{"nums":[7],"target":7}

Expected0

⏱ Performance - must finish in 2000ms

Single element array where target equals the only element at index 0.

💡 Binary search should handle single element arrays.

💡 Check if nums[0] == target and return 0.

💡 Ensure low and high pointers initialize correctly for single element.

Why it failed: Fails to find target in single element array. Possibly loop condition or mid calculation incorrect. Fix: ensure loop runs when low <= high and mid calculation correct.

✓ Correctly finds target in single element array.

t2_03edge

Input{"nums":[10,20,30,40,50],"target":5}

Expected-1

⏱ Performance - must finish in 2000ms

Target smaller than all elements returns -1.

💡 Binary search should return -1 if target not found.

💡 Check boundary conditions when target < nums[0].

💡 Ensure loop terminates correctly when target is out of range.

Why it failed: Returns index instead of -1 for target smaller than all elements. Fix: ensure return -1 if target not found after loop ends.

✓ Correctly returns -1 for target smaller than all elements.

t2_04edge

Input{"nums":[10,20,30,40,50],"target":60}

Expected-1

⏱ Performance - must finish in 2000ms

Target larger than all elements returns -1.

💡 Binary search should return -1 if target not found.

💡 Check boundary conditions when target > nums[-1].

💡 Ensure loop terminates correctly when target is out of range.

Why it failed: Returns index instead of -1 for target larger than all elements. Fix: ensure return -1 if target not found after loop ends.

✓ Correctly returns -1 for target larger than all elements.

t3_01corner

Input{"nums":[1,2,3,4,5,6,7,8,9,10],"target":11}

Expected-1

⏱ Performance - must finish in 2000ms

Target larger than all elements returns -1.

💡 Check if binary search correctly handles target > max element.

💡 Verify loop termination condition and boundary updates.

💡 Ensure return -1 if target not found after exhausting search space.

Why it failed: Returns incorrect index or infinite loop for target larger than all elements. Fix: update high = mid-1 correctly and loop condition low <= high.

✓ Correctly returns -1 for target larger than all elements.

t3_02corner

Input{"nums":[2,4,6,8,10],"target":8}

Expected3

⏱ Performance - must finish in 2000ms

Test to catch off-by-one errors in mid calculation or loop conditions.

💡 Check mid calculation carefully to avoid infinite loops.

💡 Verify low and high updates do not skip valid indices.

💡 Use mid = low + (high - low) // 2 to prevent overflow.

Why it failed: Infinite loop or wrong index due to off-by-one in mid or boundary updates. Fix: use mid = low + (high - low) // 2 and update low = mid+1 or high = mid-1 properly.

✓ Correctly handles mid calculation and loop boundaries.

t3_03corner

Input{"nums":[1,3,5,7,9,11,13],"target":7}

Expected3

⏱ Performance - must finish in 2000ms

Test to catch confusion between iterative and recursive binary search implementations.

💡 Ensure iterative binary search updates low and high correctly.

💡 If recursive, ensure base case and mid calculation are correct.

💡 Avoid mixing iterative and recursive logic in one implementation.

Why it failed: Wrong index or stack overflow due to incorrect recursion or iteration logic. Fix: implement either iterative or recursive binary search correctly with proper base cases and updates.

✓ Correctly implements binary search with consistent approach.

t4_01performance

Input{"nums":[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99,100000],"target":99999}

Expectednull

⏱ Performance - must finish in 2000ms

Large input with n=100000, binary search O(log n) must complete within 2 seconds.

💡 Binary search runs in O(log n) time.

💡 Avoid linear scans to prevent TLE.

💡 Use efficient mid calculation and loop conditions.

Why it failed: TLE due to linear search or inefficient algorithm. Fix: implement O(log n) binary search instead of O(n) linear search.

✓ Algorithm runs within time limit using O(log n) binary search.

Practice

1. Consider the following Python code using bisect to count occurrences of a target in a sorted array. What is the output when nums = [1, 2, 2, 3] and target = 2?

easy

A. 2

B. 1

C. 3

D. 0

Solution

1. Step 1: Trace bisect_left for target=2

   bisect_left(nums, 2) returns index 1 (first 2 in array).

2. Step 2: Trace bisect_left for target+1=3

   bisect_left(nums, 3) returns index 3 (first 3 in array).

3. Step 3: Calculate count

   Count = right - left = 3 - 1 = 2 occurrences.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Indices 1 and 2 are 2's in array [OK]

Hint: bisect_left finds first occurrence index [OK]

Common Mistakes:

• Confusing bisect_left with bisect_right
• Off-by-one errors in index subtraction
• Using bisect_right for target+1 incorrectly

2. 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.

Solution

1. Step 1: Understand problem constraints

   The matrix rows and columns are sorted, so each row is sorted and each column is sorted independently.

2. Step 2: Identify the optimal approach

   Using a min-heap to merge sorted rows efficiently extracts the smallest elements in ascending order, achieving O(k log n) time, better than flattening and sorting.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Min-heap merges sorted lists optimally [OK]

Hint: Min-heap merges sorted rows efficiently [OK]

Common Mistakes:

• Assuming flatten and sort is optimal
• Confusing DP with this problem
• Thinking greedy without data structures works

3. What is the time complexity of the optimal binary search algorithm that treats an m x n 2D matrix as a 1D sorted array to search for a target?

medium

A. O(log(m * n))

B. O(m * n)

C. O(m * log n)

D. O(log m + log n)

Solution

1. Step 1: Understand the search space size

   The matrix has m*n elements, treated as a sorted 1D array.

2. Step 2: Apply binary search complexity

   Binary search on an array of size m*n takes O(log(m*n)) time.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Binary search halves search space each step, log scale [OK]

Hint: Binary search complexity depends on total elements, not rows or columns separately [OK]

Common Mistakes:

• Confusing with O(m*n) brute force
• Thinking binary search per row is O(m log n)
• Adding logs incorrectly as O(log m + log n)

4. Suppose the problem is modified so that the input array arr can contain negative numbers and zero, and you still need to find the kth positive missing number (positive integers missing from the array). Which of the following changes to the optimal binary search approach is correct?

hard

A. Modify the missing count calculation to be arr[mid] - (mid + 1) + offset, where offset accounts for negative numbers.

B. No change needed; the existing binary search works as is because it only depends on indices and values.

C. Filter out non-positive numbers first, then apply the binary search approach on the filtered positive array.

D. Use the brute force linear scan approach instead, as binary search cannot handle negative numbers.

Solution

1. Step 1: Understand the problem modification

   Negative numbers and zero do not affect the count of missing positive integers, but they disrupt the assumption that arr contains only positive sorted numbers.

2. Step 2: Adjust the input for binary search

   Filtering out non-positive numbers creates a sorted array of positive integers, restoring the problem's original assumptions and enabling correct binary search.

3. Step 3: Reject other options

   No change (B) fails because negative numbers break missing count logic; offset (C) is ambiguous and error-prone; brute force (D) is inefficient and unnecessary.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   Filtering preserves correctness and efficiency [OK]

Hint: Filter positives before binary search [OK]

Common Mistakes:

• Assuming binary search works without filtering
• Trying to adjust missing count with offsets
• Switching to brute force unnecessarily

5. Suppose the problem is modified so that x can be negative, and you want to return the integer square root of its absolute value. Which modification to the Newton's method code below correctly handles this variant without breaking the algorithm?

hard

A. Remove the base case check and rely on the loop to handle all x.

B. Change the loop condition to 'while guess * guess >= x' to handle negatives.

C. Add 'x = abs(x)' at the start and keep the rest unchanged.

D. Use floating point division instead of integer division to handle negatives.

Solution

1. Step 1: Understand the problem change

   Allowing negative x means we must compute the integer square root of |x|.

2. Step 2: Modify input safely

   Adding x = abs(x) at the start ensures the algorithm works unchanged on non-negative inputs.

3. Step 3: Avoid incorrect changes

   Removing base cases or changing loop conditions breaks correctness; floating point division violates problem constraints.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   Absolute value conversion preserves algorithm correctness [OK]

Hint: Convert input to non-negative before applying integer sqrt [OK]

Common Mistakes:

• Removing base cases
• Changing loop condition incorrectly
• Using float division causing precision errors