Debugging challengeBeginner

Binary search that hangs

Scenario

A colleague reports that this binary search sometimes throws IndexError and sometimes never returns at all. The input nums is sorted ascending and may be empty. Find every bug without running the code.

Broken
1def binary_search(nums, target):
2 left = 0
3 right = len(nums)
4
5 while left <= right:
6 mid = (left + right) // 2
7
8 if nums[mid] == target:
9 return mid
10
11 if nums[mid] < target:
12 left = mid
13 else:
14 right = mid
15
16 return -1

The corrected version appears here once you have revealed everything below.

Your task

  1. Trace the code on nums = [1, 3, 5], target = 7 and on nums = [1, 3], target = 3. What happens in each case?
  2. Identify both bugs and state the loop invariant that each one breaks.
  3. Write the corrected function.
  4. List the edge cases you would test: empty array, single element, target smaller/larger than everything, duplicates.
  5. State the time and space complexity of the corrected version.
DebuggingEdge CasesSystematic Reasoning

Work it out

Write your analysis before revealing anything. The self-check below compares it against what a strong answer contains.

Reveal

Progressive — each section builds on the previous one.

The bug
Why it happens
The fix
Edge cases
Complexity
What this tests

Self-check

Tick what your analysis covered. Be honest — this feeds your readiness profile.

0/7

Related concepts