[[Arrays]]

Problem

Imagine I have a list of numbers, sorted from smallest to largest. I will not show you the list, but I will answer questions about it. Your goal is to devise a strategy to find out if a specific number, your “target,” is in my list using the minimum number of questions.

The list is: [2, 5, 8, 12, 16, 23, 38, 56, 72, 91] The list has 10 items. Indices are 0 through 9.
Your target number to find is 23.

Brainstorming

• Pre-condition: The array must be sorted.

• Core Strategy: Divide and Conquer by checking the middle element.

• Variables: You implicitly described them: a left pointer, a right pointer (which define the search space), and a mid pointer calculated from them.

• Outcomes:

  1. target == nums[mid] -> Found. Return mid.
  2. target < nums[mid] -> Search Left. The new search space becomes left to mid - 1.
  3. target > nums[mid] -> Search Right. The new search space becomes mid + 1 to right.

nums = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
target = 38


def binary_search(nums:List[int], target:int) -> bool:
	left = 0
	right = len(nums) - 1

	while left <= right:
		mid = (left + right )// 2
		
		if target == nums[mid]
			return True
		elif target > nums[mid]: # number is in the right side
			left = mid + 1
		else: # the number is in the left side
			right = mid - 1 
			
	return False

binary_search(nums, target)

Why left <= right and not left < right

lets walk this point with a concrete example. It’s a subtle but critical detail.

Your current, correct code is: while left < right: ... else: # target < nums[mid] right = mid - 1

Let’s imagine you wrote this instead (The Incorrect Version for this trace): while left < right: ... else: # target < nums[mid] right = mid

Now, let’s trace this Incorrect Version with a simple scenario where the target is not in the list, but is smaller than all remaining elements.

• nums = [8, 12]
• target = 5

Setup:

• left = 0
• right = 2 (because you initialized it to len(nums))

Iteration 1:

• while 0 < 2: (True)
• mid = (0 + 2) // 2 = 1
• nums[mid] is nums[1], which is 12.
• target (5) is less than nums[mid] (12).
• The else block is executed.
• With the incorrect code, you set right = mid, so right becomes 1.

Iteration 2:

• left is 0, right is 1.
• while 0 < 1: (True)
• mid = (0 + 1) // 2 = 0
• nums[mid] is nums[0], which is 8.
• target (5) is less than nums[mid] (8).
• The else block is executed.
• With the incorrect code, you set right = mid, so right becomes 0.

Iteration 3:

• left is 0, right is 0.
• while 0 < 0: is False. The loop terminates.
• The function returns False, which is correct.

So far, it seems to work. But let’s try a different loop condition. What if your while loop condition was while left <= right? This is a very common way to write binary search.

Let’s re-trace the Incorrect Version (right = mid) but with the while left <= right loop condition.

• nums = [8, 12]
• target = 5

Setup:

• left = 0
• right = 1 (let’s assume you fixed right to be len(nums) - 1 for this trace)

Iteration 1:

• while 0 <= 1: (True)
• mid = (0 + 1) // 2 = 0
• nums[mid] is nums[0], which is 8.
• target (5) is less than nums[mid] (8).
• The else block is executed.
• With the incorrect code, you set right = mid, so right becomes 0.

Iteration 2:

• left is 0, right is 0.
• while 0 <= 0: (True)
• mid = (0 + 0) // 2 = 0
• nums[mid] is nums[0], which is 8.
• target (5) is less than nums[mid] (8).
• The else block is executed.
• With the incorrect code, you set right = mid, so right becomes 0.

The Problem: left is 0, right is 0. You’re back in the exact same state as the start of Iteration 2. You will now loop forever. This is an infinite loop.

Conclusion: Setting right = mid - 1 (and left = mid + 1) is crucial because it guarantees that the search space is always getting smaller in every single iteration. If you set right = mid, there exists a case (when left and mid are the same) where the search space does not shrink, which can lead to an infinite loop depending on your while condition.

Your implementation with while left < right and right = len(nums) is a valid pattern (often used in C++ STL’s lower_bound), but it has to be paired with right = mid and left = mid + 1. The more common pattern, and perhaps easier to reason about, is left <= right with right = mid - 1.

Does that trace clarify why right = mid - 1 is so important for guaranteeing progress and preventing infinite loops?