Binary Search: Classic search Pattern

Learning Outcome

After this lesson, you should be able to explain why sorted order allows half the search space to be discarded at every step.

Problem Statement

Given a sorted integer array nums and a target, return the index of target. If the target is not present, return -1.

Brute Force Approach

Scan from left to right until the target is found. This is easy, but it ignores sorted order and costs O(n).

Optimized Approach

Keep two boundaries: left and right. Check the middle index. If the middle value is too small, the target can only be on the right. If it is too large, the target can only be on the left.

The key is to move boundaries past mid, otherwise the loop may never shrink.

Exact Pseudocode

left = 0
right = length(nums) - 1
while left <= right:
  mid = left + (right - left) // 2
  if nums[mid] == target:
    return mid
  if nums[mid] < target:
    left = mid + 1
  else:
    right = mid - 1
return -1
  

Reference Code

class Solution:
    def search(self, nums, target):
        left = 0
        right = len(nums) - 1

        while left <= right:
            mid = left + (right - left) // 2
            if nums[mid] == target:
                return mid
            if nums[mid] < target:
                left = mid + 1
            else:
                right = mid - 1

        return -1
  

Sample Dry Run

Complexity

Edge Cases

• Empty array or single element.
• Target at first or last index.
• Target absent and boundaries cross.

Interview Checklist

• Confirm the array is sorted.
• Use left + (right - left) / 2 for midpoint.
• Move to mid + 1 or mid - 1, not just mid.

FAQs