Skip to main content
Back to path

Welcome to a Grasp lesson

Create a free account to keep studying and create your own study path.

Lesson 6

Binary Search and Its Variations

Recommended resources

Hello! Welcome to your sixth lesson.

In our previous lesson, we dove into recursion, establishing a framework for solving problems by breaking them down into smaller, self-similar subproblems. We ended by noting that this "divide and conquer" mindset is central to many efficient algorithms.

Today, we'll explore perhaps the most classic and powerful application of this principle: Binary Search. This algorithm is a cornerstone of computer science and a fundamental pattern you'll need to master for your interviews. Its efficiency is what makes searching through massive, sorted datasets—from database indexes to company phonebooks—feasible.

Our learning outcome is to implement binary search on sorted arrays and its variations for problems like search in rotated arrays. We will start with the standard algorithm to build a solid foundation and then apply that thinking to a more complex, interview-style problem. This will perfectly illustrate how to adapt a core algorithm to a new set of constraints.

1. The Core Idea: Divide and Conquer

Binary search works on sorted arrays. The core idea is simple yet profound: instead of checking elements one by one (a linear, O(n) search), you start by checking the middle element.

  • If the middle element is your target, you're done.
  • If your target is smaller than the middle element, you know it can only be in the left half of the array.
  • If your target is larger, it can only be in the right half.

In a single step, you've eliminated half of the search space. You repeat this process on the remaining half until you find the target or the search space is empty. This repeated halving is what gives binary search its remarkable logarithmic time complexity, O(log n).

Binary Search Algorithm Visualization
This image illustrates the binary search process. Starting with the full array, the algorithm checks the middle element. Based on the comparison, it discards one half and continues the search on the remaining, much smaller, segment.

2. Standard Binary Search Implementation

While binary search can be implemented recursively (a natural fit for divide and conquer), the iterative approach is more common in production and interviews to avoid potential stack depth limits on huge datasets. Let's focus on mastering the iterative version.

This video provides an excellent, clear walkthrough of the implementation.

Binary Search - Leetcode 704 - Python

Let's start with the fundamental iterative implementation of binary search. This video from NeetCode provides a clear walkthrough of the logic, pointer manipulation, and time complexity.

Watch from the beginning to 07:28. Pay close attention to: How the left and right pointers define the search space. The logic for updating these pointers based on the comparison with the middle element. The explanation for why the time complexity is O(log n). The while left <= right loop condition and why the equality is important.

Implementation Details and Pitfalls

As the video mentions, the details matter. A slightly off-by-one error in the loop condition or pointer updates can lead to bugs or infinite loops.

  • Loop Condition: Using while (left <= right) is crucial. If you use left < right, the loop will terminate when left and right point to the same element, and you'll fail to check the last remaining candidate.
  • Pointer Updates: When you discard a half, you must move the pointers past the middle element: left = mid + 1 or right = mid - 1. If you set right = mid, you might get stuck in an infinite loop.
  • Integer Overflow: Calculating the middle index as mid = (left + right) / 2 can cause an integer overflow in languages like C++ or Java if left and right are very large positive numbers. The safer way, mid = left + (right - left) / 2, avoids this by calculating the offset from left. While Python's arbitrary-precision integers make this a non-issue, it's a detail worth knowing for interviews, as it demonstrates a deeper understanding of computational constraints.

This next reading from TopCoder, a well-regarded resource in the competitive programming community, formalizes some of these key implementation details.

Binary Search - Competitive Programming Tutorials

Now that you've seen a practical implementation, let's explore some of the subtleties and best practices for writing robust binary search code.

Read the sections 'Finding a value in a sorted sequence' and 'Implementing the discrete algorithm'. Focus on: The concept of the 'search space' as an invariant. The importance of how you move the bounds (hi = mid vs. lo = mid + 1). The discussion on avoiding infinite loops by carefully choosing the mid calculation and bound updates.

3. Variation: Search in a Rotated Sorted Array

Now for the interesting part. What if the sorted array was "rotated" at some unknown pivot point?
For example, [0, 1, 2, 4, 5, 6, 7] might become [4, 5, 6, 7, 0, 1, 2].

A linear scan would work but is O(n). The challenge is to solve this in O(log n) time. A standard binary search will fail because the array is no longer fully sorted. However, we can adapt our logic.

The Key Insight: When you split a rotated sorted array at a middle point, at least one of the two halves will be perfectly sorted.

Binary Search in Rotated Sorted Array: Code and Visual Explanation
This diagram summarizes the logic for searching in a rotated sorted array. On the left is the Python code, and on the right are visualizations that show how to identify the sorted half and where the target might lie, guiding the adjustment of the `l` and `r` pointers.

Our modified algorithm is:

  1. Perform binary search, calculating mid.
  2. Identify which half is sorted. For example, if nums[left] <= nums[mid], the left half is sorted. Otherwise, the right half is.
  3. Check if the target lies within the range of the sorted half.
    • If yes, search within that sorted half (by adjusting left or right).
    • If no, the target must be in the other, unsorted half, so search there.

This strategy guarantees we can still discard half the search space at every step. Let's see it in action.

Search in rotated sorted array - Leetcode 33 - Python

This video from NeetCode explains the clever modification to the binary search logic required to solve this classic interview problem.

Watch the video up to 12:51. Focus on the core decision-making process: How to identify which side of the middle element is sorted. How to decide whether to search the sorted side or the other side, based on the target's value.

To reinforce this, the following reading provides a detailed textual breakdown and highlights common mistakes, which is excellent preparation for thinking through edge cases in an interview.

33. Search in Rotated Sorted Array - Detailed Explanation

To solidify your understanding, this article provides a detailed step-by-step breakdown of the same logic, along with common pitfalls and edge cases. It's a great reference to review.

Read the sections 'Optimized Binary Search Approach' and 'Common Mistakes & Edge Cases'. This will reinforce the algorithm and highlight potential bugs to watch out for.

Test your understanding!

Consider the rotated array nums = [7, 8, 1, 2, 3, 4, 5, 6] and target = 8.

Walk through the first two steps of the modified binary search. What will be the left, right, and mid indices after the first iteration?

Show answer

Initial State:

  • left = 0, right = 7
  • mid = 0 + (7 - 0) // 2 = 3
  • nums[mid] is nums[3], which is 2.

First Iteration Logic:

  1. Which half is sorted? We compare nums[left] (7) with nums[mid] (2). Since 7 > 2, the left half [7, 8, 1, 2] is not sorted. This means the right half, [2, 3, 4, 5, 6], must be sorted.
  2. Where is the target? Our target is 8. We check if it's in the sorted right half. The range of the sorted right half is from nums[mid] (2) to nums[right] (6). Is 8 between 2 and 6? No.
  3. Update pointers: Since the target is not in the sorted right half, it must be in the unsorted left half. We discard the right half by setting right = mid - 1.

State after first iteration:

  • left = 0
  • right = 2 (was 7, now mid - 1 = 3 - 1 = 2)

The new search space is [7, 8, 1].

Conclusion

Today you've tackled one of the most fundamental algorithms in computer science. You not only learned its standard implementation but also saw how to adapt its core "divide and conquer" principle to a non-obvious problem.

Key Takeaways:

  • Binary search provides O(log n) time complexity for searching in sorted data structures with random access.
  • The iterative implementation is standard. Careful management of loop conditions (left <= right) and pointer updates (mid - 1, mid + 1) is critical to avoid bugs.
  • For variations like a rotated array, the key is to find an invariant property (e.g., "one half is always sorted") that allows you to reliably discard half the search space in each step. Being able to derive this logic is a hallmark of strong problem-solving skills.

In our next lesson, we will formalize an idea we've touched upon: time-space trade-offs. For example, to use binary search, we need a sorted array. Sorting takes O(n log n) time. Alternatively, we could use a hash map to get O(1) average lookups, but that requires O(n) space. When is one approach better than the other? We will explore this critical aspect of algorithm design next.