Why Binary Search Practice Matters

Binary search isn’t just about finding a number in a sorted array. The same logarithmic principle applies to:

• Finding boundaries (first/last occurrence)
• Searching in rotated arrays
• Optimization problems (e.g., “find minimum capacity”)
• Mathematical approximations (square roots, logarithms)
  Working through binary search exercises trains you to:
• Recognize when O(log n) is achievable
• Handle boundary conditions confidently
• Write bug-free, production-ready code
  Before we start, make sure you’ve reviewed Handling Binary Search Edge Cases & Boundary Conditions. Many of the problems below fail on edge cases if you don’t.

Problem 1: Classic Binary Search (Find Target)

Difficulty: Easy
Problem Statement: Given a sorted array of integers nums and a target integer target, return the index of target if it exists. Otherwise, return -1.

This is the quintessential binary search practice problem.

Solution Approach

We maintain two pointers: left and right. At each step, compute mid = (left + right) // 2. If nums[mid] == target, return mid. If target < nums[mid], search the left half; otherwise, search the right half.

Code Example (Python)

def binary_search(nums, target):
    left, right = 0, len(nums) - 1

    while left <= right:
        mid = (left + right) // 2

        if nums[mid] == target:
            return mid
        elif target < nums[mid]:
            right = mid - 1
        else:
            left = mid + 1

    return -1

# Test
print(binary_search([1, 3, 5, 7, 9], 5))  # Output: 2
print(binary_search([1, 3, 5, 7, 9], 2))  # Output: -1

Edge Cases to Consider

• Empty array → return -1
• Target smaller than all elements → final right becomes -1
• Target larger than all elements → final left becomes len(nums)

Time & Space Complexity

• Time: O(log n)
• Space: O(1)
  For a deeper understanding of why left <= right matters (and not just left < right), review our Debugging Binary Search Implementations: Common Bugs & Fixes.

Problem 2: First and Last Position of Target

Difficulty: Medium
Problem Statement: Given a sorted array nums with possible duplicates and a target, find the first and last index where target appears. Return [-1, -1] if not found.

This binary search coding challenge requires two passes: one to find the left boundary, another for the right boundary.

Solution Approach

We can’t just stop at the first match because duplicates exist. Instead:

1. Find leftmost index: When nums[mid] == target, set right = mid (continue searching left).
2. Find rightmost index: When nums[mid] == target, set left = mid + 1 (continue searching right).

Code Example (Python)

def search_range(nums, target):
    def find_boundary(is_left):
        left, right = 0, len(nums) - 1
        result = -1
        while left <= right:
            mid = (left + right) // 2
            if nums[mid] == target:
                result = mid
                if is_left:
                    right = mid - 1
                else:
                    left = mid + 1
            elif target < nums[mid]:
                right = mid - 1
            else:
                left = mid + 1
        return result

    return [find_boundary(True), find_boundary(False)]

# Test
print(search_range([5,7,7,8,8,10], 8))  # Output: [3, 4]
print(search_range([5,7,7,8,8,10], 6))  # Output: [-1, -1]

Why Two Searches?

A single binary search cannot simultaneously find the first and last occurrence without post-processing, which could degrade to O(n) in a worst-case duplicate scenario.

This problem frequently appears in binary search practice problems and solutions collections because it tests your ability to modify the standard algorithm.

Related Resource

Pair this exercise with Master Algorithm Implementation for Coding Interviews | Guide to see how binary search fits into a broader interview strategy.

Problem 3: Search in Rotated Sorted Array

Difficulty: Medium
Problem Statement: An array sorted in ascending order is rotated at an unknown pivot (e.g., [0,1,2,4,5,6,7] becomes [4,5,6,7,0,1,2]). Search for a target in O(log n) time.

This is a classic binary search exercise that tests your ability to identify which half of the array is normally sorted.

Solution Approach

At each mid, at least one half of the array is fully sorted (left of pivot or right of pivot). We check:

• If the left half is sorted (nums[left] <= nums[mid]):If target lies within that sorted range, search left; otherwise, search right.
  Else the right half is sorted.

Code Example (Python)

def search_rotated(nums, target):
    left, right = 0, len(nums) - 1

    while left <= right:
        mid = (left + right) // 2

        if nums[mid] == target:
            return mid

        # Left half is sorted
        if nums[left] <= nums[mid]:
            if nums[left] <= target < nums[mid]:
                right = mid - 1
            else:
                left = mid + 1
        # Right half is sorted
        else:
            if nums[mid] < target <= nums[right]:
                left = mid + 1
            else:
                right = mid - 1
    return -1

# Test
print(search_rotated([4,5,6,7,0,1,2], 0))  # Output: 4
print(search_rotated([4,5,6,7,0,1,2], 3))  # Output: -1

Common Pitfall

Failing to handle duplicate values. If duplicates exist, the condition nums[left] <= nums[mid] may not guarantee a sorted left half. For duplicates, additional checks are needed (though that problem is often called “Search in Rotated Sorted Array II”).

How This Builds Your Skills

Unlike standard binary search practice problems, this one forces you to reason about partial order. The skill transfers directly to Real-World Applications of Binary Search | Efficiency & Problem-Solving, where data isn’t always perfectly sorted.

Problem 4: Find Peak Element

Difficulty: Medium
Problem Statement: A peak element is strictly greater than its neighbors. Given an array nums (which may have multiple peaks), return the index of any peak in O(log n) time. You may assume nums[-1] = nums[n] = -∞.

This problem surprises many students because the array is not fully sorted — yet binary search still works.

Solution Approach

We don’t need to find the global maximum; any local peak suffices. At mid:

• If nums[mid] > nums[mid + 1], a peak exists on the left (including mid).
• Otherwise, a peak exists on the right.
  This works because the array ends are negative infinity, guaranteeing at least one peak.

Code Example (Python)

def find_peak(nums):
    left, right = 0, len(nums) - 1

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

# Test
print(find_peak([1,2,3,1]))   # Output: 2 (value 3)
print(find_peak([1,2,1,3,5,6,4]))  # Output: 5 (value 6) or 1

Why Binary Search Works on Unsorted Data

Binary search only requires a monotonic condition on which direction to move. Here, the condition is “if mid is in a decreasing slope, move left; else move right.”

This problem appears in many binary search coding challenges because it breaks the misconception that binary search requires total order.

Debugging Tip

Run through a small example on paper. For [1,2,3,1]:

• left=0, right=3, mid=1 → 2 > 1? No → move left to 2
• left=2, right=3, mid=2 → 3 > 1? Yes → move right to 2
• Loop ends, return 2.
  For more debugging strategies, see Debugging Python Code Like a Pro: Tips & Tricks.

Problem 5: Square Root Approximation

Difficulty: Easy–Medium
Problem Statement: Given a non-negative integer x, return the integer part of its square root (floor of √x) without using built-in exponent functions. Use O(log x) time.

This is a different flavor of binary search exercise — searching on the answer space, not the input array.

Solution Approach

We binary search over the range [0, x]. For each mid, compute mid * mid:

• If mid * mid == x → return mid
• If mid * mid < x → need larger root → left = mid + 1
• If mid * mid > x → need smaller root → right = mid - 1
  We return right at the end because the loop exits when left > right, and right holds the largest integer whose square ≤ x.

Code Example (Python)

def sqrt_int(x):
    if x < 2:
        return x

    left, right = 0, x
    while left <= right:
        mid = (left + right) // 2
        square = mid * mid
        if square == x:
            return mid
        elif square < x:
            left = mid + 1
        else:
            right = mid - 1
    return right

# Test
print(sqrt_int(8))   # Output: 2 (since 2^2=4, 3^2=9>8)
print(sqrt_int(16))  # Output: 4

Why This Matters

Many optimization problems — like finding minimum capacity to ship packages within D days — use binary search on the answer rather than the input. Mastering binary search practice problems and solutions of this type prepares you for those advanced scenarios.

Performance Note

The loop runs O(log x) times. For x = 2^31 - 1, that’s only ~31 iterations.

Common Mistakes & Debugging

Even after practicing binary search exercises, students often stumble on the same issues:

1. Infinite Loops

• Cause: Using while left < right but not updating boundaries correctly.
• Fix: Test with array length 2. If left=0, right=1, mid=0, ensure you don’t get stuck.

2. Off-by-One in Mid Calculation

• Cause: Using mid = (left + right) // 2 in all cases. For right-biased searches, use mid = (left + right + 1) // 2.
• Fix: Know when you need the upper mid (e.g., finding last occurrence).

3. Integer Overflow (Not in Python)

• 📝 Note: In languages like Java/C++, (left + right) // 2 can overflow. Use left + (right - left) // 2.