Binary Search

▶

Steps

setup

Initialize search boundaries

We start the binary search with the entire array as the search space, setting low to 0 and high to the last index.

💡 Setting the initial boundaries is crucial because binary search works by narrowing this range until the target is found or the range is empty.

Line:

def binary_search_recursive(nums, target, low, high):
    if low > high:
        return -1

💡 The search space initially covers the whole array.

compare

Calculate mid index

Calculate mid as the average of low and high: mid = 0 + (5 - 0) // 2 = 2.

💡 Finding the middle index allows us to check the middle element and decide which half to search next.

Line:

    mid = low + (high - low) // 2

💡 Mid index divides the current search space into two halves.

compare

Compare mid value with target

Compare nums[mid] = 3 with target = 9. Since 3 < 9, the target must be in the right half.

💡 This comparison tells us which half of the array to discard, reducing the search space efficiently.

Line:

    if nums[mid] == target:
        return mid
    elif nums[mid] < target:

💡 The left half including mid can be eliminated because target is greater than mid value.

traverse

Recurse on right half

Update low to mid + 1 = 3, keeping high at 5, and recurse to search in the right half.

💡 Adjusting the search boundaries focuses the search on the half where the target can still be found.

Line:

        return binary_search_recursive(nums, target, mid + 1, high)

💡 The search space is now narrowed to indices 3 through 5.

compare

Calculate mid index in right half

Calculate mid = 3 + (5 - 3) // 2 = 4 to check the middle element of the new search space.

💡 Recalculating mid is necessary to continue the binary search in the updated range.

Line:

    mid = low + (high - low) // 2

💡 Mid now points to index 4 in the narrowed search space.

compare

Compare mid value with target

Compare nums[mid] = 9 with target = 9. They are equal, so the target is found at index 4.

💡 Finding the target means the search can stop and return the index immediately.

Line:

    if nums[mid] == target:
        return mid

💡 The target is located at mid index 4.

reconstruct

Return the found index

Return index 4 as the position of the target in the array.

💡 Returning the index completes the search and provides the answer.

Line:

        return mid

💡 The algorithm successfully found the target and returns its index.

reconstruct

Final answer confirmed

The search is complete and the target index 4 is confirmed as the output.

💡 The final step shows the result of the binary search after all recursive calls.

Line:

print(binary_search_recursive(nums, target, 0, len(nums) - 1))  # Output: 4

💡 The target 9 is at index 4 in the array.

prune

Summary of search space narrowing

The search space was narrowed from indices 0-5 to 3-5, then to index 4 where the target was found.

💡 This step summarizes how the algorithm pruned the search space efficiently.

💡 Binary search eliminates half the search space each step, leading to O(log n) time complexity.

reconstruct

End of binary search

The algorithm terminates with the target found at index 4, completing the search.

💡 This final step confirms the successful completion of the binary search process.

💡 Binary search returns the correct index or -1 if the target is not found.

def binary_search_recursive(nums, target, low, high):  # STEP 1
    if low > high:  # STEP 1
        return -1
    mid = low + (high - low) // 2  # STEP 2,5
    if nums[mid] == target:  # STEP 3,6
        return mid  # STEP 6,7
    elif nums[mid] < target:  # STEP 3
        return binary_search_recursive(nums, target, mid + 1, high)  # STEP 4
    else:
        return binary_search_recursive(nums, target, low, mid - 1)

if __name__ == '__main__':
    nums = [-1,0,3,5,9,12]
    target = 9
    print(binary_search_recursive(nums, target, 0, len(nums) - 1))  # STEP 8

📊

Binary Search - Watch the Algorithm Execute, Step by Step

Watching the algorithm step-by-step reveals how the pointers move and how the search space shrinks, making it easier to understand the logic behind binary search than just reading code.

Target: 9

lo

-1

0

0

1

3

2

5

3

9

4

hi

12

5

Next: lo=0 hi=5

Target: 9

lo

-1

0

0

1

mid

3

2

5

3

9

4

hi

12

5

mid[2]=3 - mid value 3 compared to target 9

Next: lo=0 hi=5

Target: 9

lo

-1

0

0

1

mid

3

2

5

3

9

4

hi

12

5

mid[2]=3 - 3 < 9, discard left half including mid

Next: lo=3 hi=5

Target: 9

-1

0

0

1

3

2

lo

5

3

9

4

hi

12

5

Next: lo=3 hi=5

Target: 9

-1

0

0

1

3

2

lo

5

3

mid

9

4

hi

12

5

mid[4]=9 - mid value 9 compared to target 9

Next: lo=3 hi=5

Target: 9

-1

0

0

1

3

2

lo

5

3

mid

9

4

hi

12

5

mid[4]=9 - 9 == 9, target found

Next: lo=3 hi=5

Target: 9

-1

0

0

1

3

2

lo

5

3

mid

9

4

hi

12

5

mid[4]=9 - target found at index 4

Next: lo=3 hi=5

Target: 9

lo

-1

0

0

1

3

2

5

3

mid

9

4

hi

12

5

mid[4]=9 - target found at index 4

Next: lo=4 hi=4

Target: 9

-1

0

0

1

3

2

5

3

lo/mid/hi

9

4

12

5

mid[4]=9 - final step, target found

Next: lo=4 hi=4

Target: 9

-1

0

0

1

3

2

5

3

lo/mid/hi

9

4

12

5

mid[4]=9 - target found, search complete

Next: lo=4 hi=4

Key Takeaways

✓ Binary search efficiently narrows the search space by half each step using mid comparisons.

This efficiency is hard to grasp from code alone but clear when watching the search space shrink visually.

✓ The mid pointer dynamically adjusts to the current search boundaries, guiding the search direction.

Seeing mid move helps understand how the algorithm divides the array logically.

✓ The decision to discard either the left or right half depends solely on the comparison between nums[mid] and the target.

Visualizing this decision clarifies why binary search is faster than linear search.

Practice

1. The following code attempts to find the kth positive missing number from a sorted array arr. Which line contains a subtle bug that causes incorrect results for some inputs?

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  # Bug here
        if missing < k:
            left = mid + 1
        else:
            right = mid - 1
    return arr[right] + (k - (arr[right] - (right + 1)))

medium

A. Line returning arr[right] + (k - (arr[right] - (right + 1)))

B. Line calculating total_missing = arr[-1] - n

C. Line updating left = mid + 1

D. Line calculating missing = arr[mid] - mid

Solution

1. Step 1: Identify the missing count formula

   The correct missing count at index mid is arr[mid] - (mid + 1), since indices are zero-based but numbers start at 1.

2. Step 2: Analyze the bug impact

   Using arr[mid] - mid undercounts missing numbers by 1, causing incorrect binary search decisions and wrong final result.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Correct missing count formula is arr[mid] - (mid + 1) [OK]

Hint: Missing count must subtract (mid + 1), not mid [OK]

Common Mistakes:

• Off-by-one in missing count calculation
• Incorrect binary search boundary updates
• Ignoring missing numbers before first element

2. What is the time complexity of the optimal binary search solution for the Minimum Days to Make m Bouquets problem, given n flowers and day range D = maxDay - minDay?

medium

A. O(n * D) because we check each day sequentially and scan all flowers.

B. O(n log D) because binary search reduces day range and each feasibility check scans n flowers.

C. O(log n * D) because binary search is on flowers and day range is scanned.

D. O(n + D) because we combine linear scans of flowers and days.

Solution

1. Step 1: Identify outer loop complexity

   Binary search runs in O(log D) iterations, where D is the day range.

2. Step 2: Identify inner loop complexity

   Each feasibility check scans all n flowers in O(n) time.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Combining gives O(n log D), not O(n * D) or others. [OK]

Hint: Binary search log factor times linear feasibility check [OK]

Common Mistakes:

• Confusing linear scan over days as O(n*D)
• Mixing binary search on flowers instead of days

3. Suppose the problem is modified so that packages can be shipped in any order (not necessarily the given order) within the given days. Which of the following approaches correctly finds the minimal ship capacity under this new constraint?

hard

A. Use dynamic programming to assign packages to days minimizing maximum load per day, combined with binary search on capacity

B. Sort packages in descending order and use a greedy bin-packing heuristic combined with binary search on capacity

C. Use a simple greedy approach assigning packages to days in any order without binary search

D. Use the same binary search on capacity with the original feasibility check since order doesn't matter

Solution

1. Step 1: Understand the relaxed constraint

   Packages can be shipped in any order, so the problem becomes a variant of multi-way partition or bin packing minimizing max load.

2. Step 2: Identify correct approach

   Binary search on capacity still applies, but feasibility check requires DP or backtracking to assign packages optimally to days, as greedy heuristics may fail.

3. Step 3: Why other options fail

   Original feasibility check assumes fixed order; greedy heuristics are approximate and may not find minimal capacity.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   DP feasibility check with binary search needed for unordered assignment [OK]

Hint: Order relaxation requires DP feasibility check, not simple greedy [OK]

Common Mistakes:

• Using original feasibility check ignoring order change
• Assuming greedy suffices
• Ignoring complexity increase

4. Suppose the array is no longer sorted but you still need to find the first and last positions of a target value. Which approach is correct and efficient?

hard

A. Use a linear scan to find first and last occurrences directly

B. Sort the array first, then apply modified binary search to find positions

C. Use the same modified binary search approach since it works on any array

D. Use a hash map to store all indices of each value, then retrieve target positions

Solution

1. Step 1: Recognize that binary search requires sorted array

   Without sorting, binary search cannot guarantee correct positions.

2. Step 2: Evaluate alternatives

   Sorting changes indices, so linear scan or hash map are options; linear scan is simplest and O(n).

3. Step 3: Compare efficiency and correctness

   Linear scan finds first and last positions in one pass without modifying array.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Binary search requires sorted input; linear scan works otherwise [OK]

Hint: Binary search needs sorted array; linear scan works otherwise [OK]

Common Mistakes:

• Trying binary search on unsorted array
• Sorting and losing original indices
• Overcomplicating with hash maps

5. Suppose the problem is modified so that each number in the array can be divided multiple times (reuse allowed), and the sum of all ceiling divisions must still be ≤ threshold. Which modification to the algorithm is necessary to correctly find the smallest divisor?

hard

A. Use the same binary search with feasibility function, but modify feasibility to count repeated divisions per element

B. Switch to a greedy approach that picks divisors based on the largest elements first

C. Use dynamic programming to track all possible divisor sums with reuse

D. Binary search is no longer applicable; use brute force over all divisors

Solution

1. Step 1: Understand the reuse modification

   Allowing multiple divisions per element means feasibility must consider repeated divisions, but the divisor search space remains monotonic.

2. Step 2: Adapt feasibility function

   Modify feasibility to count how many times each element can be divided by the divisor (e.g., sum of ceiling divisions with reuse).

3. Step 3: Retain binary search on answer space

   Binary search still applies because the feasibility condition remains monotonic with divisor.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Binary search with adapted feasibility handles reuse -> [OK]

Hint: Reuse changes feasibility, not binary search applicability [OK]

Common Mistakes:

• Discarding binary search prematurely
• Using greedy which breaks global constraints
• Overcomplicating with DP when not needed