Binary Search

Binary Search is one of the highest-ROI topics for coding interviews. It’s fast, elegant, and shows up frequently: searching in sorted arrays, finding boundaries, answer space problems, optimization, and even graphs/DP when you spot the right monotonic behavior.

At its core, Binary Search transforms a linear search, checking every single item, into a lightning-fast process that can find an element in a list of billions in just a few dozen steps. It achieves this by discarding half of the remaining search space at every step, using comparisons to decide which half can be ignored.

If you get comfortable with when binary search applies and how to write it without bugs, you’ll solve a big chunk of LeetCode efficiently and confidently.

The real-world intuition

Imagine you are looking for the word “Marmot” in a physical dictionary. As you know the word starts with the letter ‘M’, you don’t start your search with page 1 and flipping through the ‘A’s. You know the book is sorted alphabetically, so you use that structure to your advantage by starting much further in.

To begin, you open the dictionary roughly to the middle and check the words on that page. Let’s say you land on a section where the words start with “Me…”. You compare your target, “Ma”, to what you see on the page. As “Ma” comes before “Me” in the alphabet, you know with absolute certainty that “Marmot” must be located in the pages to your left.

At this point, you effectively discard the entire right half of the book from your search. You then take the remaining section of pages on the left, split them in the middle again, and repeat the same logic. By choosing a direction and eliminating half of the remaining search space at every single step, you find your target really quickly. This process is exactly how Binary Search works.

What is Binary Search?

Binary Search is a divide-and-conquer searching algorithm that finds a target value (or target position) in a sorted sequence by repeatedly comparing the target to the middle element and eliminating half of the remaining search range each step.

Why is Binary Search powerful?

Which data structures works well with Binary Search?

Binary Search works best on data structures that provide sorted order and fast random access, so we can jump directly to the middle element.

• Arrays/Dynamic Arrays (best fit): Works extremely well on arrays (and array-likes such as Python lists, Java arrays, C++ vectors) because you can access the middle element in O(1) time.
• Sorted 2D Arrays/Matrices (common variation): Works when the matrix is sorted in a way that allows binary search, for example when each row is sorted and rows are ordered, or when you apply binary search per row.
• Binary Search Trees (BSTs): BSTs are conceptually “binary search” structures because left < root < right, but searching in a BST is not the binary search algorithm on an array. Also, in an unbalanced BST, search can degrade to O(n).

How does Binary Search work?

Binary Search maintains a shrinking window of where the answer could still be using two pointers:

• low: Initialized at the start of the search range.
• high: Initialized at the end of the search range

The main steps of the Binary Search are as follows:

1. Compute the midpoint as mid = low + (high – low) // 2.
2. Compare the value pointed by the mid with the target value:
   1. If both are equal, return the mid.
   2. If the value at mid < target, the target must be in the right half, so move the low pointer forward low = mid + 1.
   3. If the value at mid > target, the target must be in the left half, so move the high pointer backward high = mid – 1.
3. Repeat until the window is empty, i.e., low > high.

Let’s look at the following illustration to get a better understanding of the Binary Search algorithm:

1 / 5

Binary Search template in Python (interview-ready)

In interviews, it helps to memorize a clean, reusable template. Here is the classic exact match template (works when the array is sorted and you want the index of the target):

def binarySearch(nums, target):
    low = 0
    high = len(nums) - 1
    
    while low <= high:
        mid = low + (high - low) // 2
        
        if nums[mid] == target:
            return mid  # Target found
        elif nums[mid] < target:
            low = mid + 1  # Search right half
        else:
            high = mid - 1  # Search left half
            
    return -1  # Target not found

Complexity analysis for Binary Search

• Time complexity (O(log n): Each iteration of binary search cuts the search space in half, so the number of comparisons grows logarithmically with the size of the input.
• Space complexity O(1): The iterative implementation uses only a constant amount of extra memory, relying on a few pointers (low, high, and mid) regardless of input size.

Modified Binary Search

In many coding interview problems, the input is not a perfectly sorted array. Instead, it has some structure that still lets you discard half the search space. This is where Modified Binary Search comes in: you keep the binary search framework, but tweak the “which half to discard?” logic based on the problem’s structure.

Classic example: Search in Rotated Sorted Array

A classic example is LeetCode 33 (Search in Rotated Sorted Array), where you search for a target in a rotated sorted array (the array is sorted but then rotated at an unknown pivot), such as:

nums = [4, 5, 6, 7, 0, 1, 2]

Even though it’s rotated, one important fact remains true: At least one half (left or right) is still sorted in every iteration.

So, instead of directly deciding which side to search in, left or right, based only on nums[mid] and target, we first identify the sorted half and use that to guide the search.

Step by step solution

1. Start with the full range of the array and compute the middle index. If nums[mid] equals the target, return mid.
2. Next, determine which half is sorted:
   1. If nums[low] <= nums[mid], the left half (low..mid) is sorted. Check whether the target lies within this sorted range (nums[low] <= target < nums[mid]).
      1. If yes, move left (high = mid - 1).
      2. If no, move right (low = mid + 1).
   2. Otherwise, the right half (mid..high) is sorted. Check whether the target lies within this sorted range (nums[mid] < target <= nums[high]).
      1. If yes, move right (low = mid + 1).
      2. If no, move left (high = mid - 1).
3. Repeat until the search range becomes invalid (low > high). If the target is not found, return -1.

This keeps the same binary search framework, but modifies the decision step to account for rotation, hence Modified Binary Search.

Python implementation

Now, let’s look at the optimized solution code for Search in Rotated Sorted Array.

def searchRotated(nums, target):
    low, high = 0, len(nums) - 1  # search range: [low ... high]

    while low <= high:
        # 1) Pick the middle element of the current range
        mid = low + (high - low) // 2

        # 2) If we found the target, return immediately
        if nums[mid] == target:
            return mid

        # 3) Decide which half is sorted
        # If nums[low] <= nums[mid], then the LEFT half [low..mid] is sorted
        if nums[low] <= nums[mid]:
            # 4) Check if target lies inside the sorted left half
            if nums[low] <= target < nums[mid]:
                # Target is in left half, shrink to [low..mid-1]
                high = mid - 1
            else:
                # Target is in right half, shrink to [mid+1..high]
                low = mid + 1
        else:
            # Otherwise, the RIGHT half [mid..high] is sorted
            # 4) Check if target lies inside the sorted right half
            if nums[mid] < target <= nums[high]:
                # Target is in right half, shrink to [mid+1..high]
                low = mid + 1
            else:
                # Target is in left half, shrink to [low..mid-1]
                high = mid - 1

    # 5) If the range becomes invalid, target isn't present
    return -1


# Driver code
def main():
    test_cases = [
        ([4, 5, 6, 7, 0, 1, 2], 0),      # target exists (rotated)
        ([4, 5, 6, 7, 0, 1, 2], 3),      # target does not exist
        ([1], 1),                         # single element (found)
        ([1], 0),                         # single element (not found)
        ([6, 7, 8, 1, 2, 3, 4, 5], 3),   # rotated, target in right sorted half
    ]

    for i, (nums, target) in enumerate(test_cases, 1):
        result = searchRotated(nums, target)
        print(f"{i}.\tnums = {nums}")
        print(f"\ttarget = {target}")
        print(f"\n\tOutput index: {result}")
        print("-" * 100)


if __name__ == "__main__":
    main()

Common Binary Search use cases

Binary Search appears in many forms across coding interviews, often hidden behind different problem statements. Recognizing these common use cases helps you quickly identify when binary search is the right tool and apply the correct pattern with confidence.