Binary Search

Introduction

Binary Search is one of the most fundamental and efficient algorithms in computer science. It’s a divide-and-conquer algorithm that searches for a target value in a sorted array by repeatedly dividing the search space in half. With a time complexity of O(log n), it’s significantly faster than linear search for large datasets.

In this article, we’ll explore Binary Search concepts through practical LeetCode problems, providing clean, well-explained solutions in both C# and Python.

What is Binary Search?

Binary Search is an algorithm that finds the position of a target value within a sorted array by:

• Comparing the target with the middle element
• If they match, return the position
• If target is smaller, search the left half
• If target is larger, search the right half
• Repeat until found or search space is exhausted

Key Requirements:

1. Sorted Array: The array must be sorted (ascending or descending)
2. Random Access: Must be able to access elements by index
3. Comparable Elements: Elements must be comparable

Time Complexity:

• Best Case: O(1) – target is at the middle
• Average Case: O(log n) – target is found after log₂(n) comparisons
• Worst Case: O(log n) – target is at the edge or not found

Space Complexity:

• Iterative: O(1) – only using a few variables
• Recursive: O(log n) – recursion stack depth

Binary Search Template

The standard binary search template uses three pointers:

• left: Left boundary of search space
• right: Right boundary of search space
• mid: Middle element

int left = 0, right = nums.Length - 1;
while (left <= right) {
    int mid = left + (right - left) / 2;
    if (nums[mid] == target) return mid;
    else if (nums[mid] < target) left = mid + 1;
    else right = mid - 1;
}
return -1; // Not found

Important: Use left + (right - left) / 2 instead of (left + right) / 2 to avoid integer overflow.

Problem 1: Search Insert Position

Problem Statement

Given a sorted array of distinct integers and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

You must write an algorithm with O(log n) runtime complexity.

Examples

Input: nums = [1,3,5,6], target = 5
Output: 2

Input: nums = [1,3,5,6], target = 2
Output: 1

Input: nums = [1,3,5,6], target = 7
Output: 4

Understanding the Problem

We need to find the insertion position for a target in a sorted array. This is essentially finding the leftmost position where we can insert the target while maintaining sorted order.

Solution Strategy

Modified Binary Search:

1. Use binary search to find the position
2. If nums[mid] >= target, the insertion point is at mid or to the left
3. If nums[mid] < target, the insertion point is to the right
4. When left == right, we’ve found the insertion position

C# Solution

public class Solution 
{
    public int SearchInsert(int[] nums, int target) 
    {
        // Binary search with O(log n) complexity
        int left = 0, right = nums.Length;
        
        while (left < right)
        {
            // Calculate middle to avoid overflow
            int mid = left + (right - left) / 2;
            
            if (nums[mid] >= target)
            {
                // Target is at mid or to the left
                right = mid;
            }
            else
            {
                // Target is to the right
                left = mid + 1;
            }
        }
        
        return left;
    }
}

Python 3 Solution

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        left = 0
        right = len(nums)
        
        while left < right:
            middle = left + (right - left) // 2
            
            if nums[middle] >= target:
                right = middle
            else:
                left = middle + 1
        
        return left

Complexity Analysis

• Time Complexity: O(log n) where n is the length of nums
• Space Complexity: O(1)

Problem 2: Find Minimum in Rotated Sorted Array

Problem Statement

Suppose an array of length n sorted in ascending order is rotated between 1 and n times. For example, the array nums = [0,1,2,4,5,6,7] might become:

• [4,5,6,7,0,1,2] if it was rotated 4 times
• [0,1,2,4,5,6,7] if it was rotated 7 times

Given the sorted rotated array nums of unique elements, return the minimum element of this array.

You must write an algorithm that runs in O(log n) time.

Example

Input: nums = [3,4,5,1,2]
Output: 1
Explanation: The original array was [1,2,3,4,5] rotated 3 times.

Understanding the Problem

In a rotated sorted array, there’s a pivot point where the array was rotated. The minimum element is at this pivot. The array has two sorted portions, and we need to find where the rotation occurred.

Solution Strategy

Binary Search for Pivot:

1. Compare nums[mid] with nums[right]
2. If nums[mid] > nums[right], the pivot is in the right half (including mid)
3. If nums[mid] <= nums[right], the pivot is in the left half (including mid)
4. When left == right, we’ve found the minimum

C# Solution

public class Solution 
{
    public int FindMin(int[] nums) 
    {
        int left = 0, right = nums.Length - 1;
        
        while (left < right)
        {
            int mid = left + (right - left) / 2;
            
            // If middle is greater than right, pivot is in right half
            if (nums[mid] > nums[right])
            {
                left = mid + 1;
            }
            else
            {
                // Pivot is in left half (including mid)
                right = mid;
            }
        }
        
        return nums[left];
    }
}

Python 3 Solution

class Solution:
    def findMin(self, nums: List[int]) -> int:
        left = 0
        right = len(nums) - 1
        
        while left < right:
            middle = left + (right - left) // 2
            
            if nums[middle] > nums[right]:
                left = middle + 1
            else:
                right = middle
        
        return nums[left]

Complexity Analysis

• Time Complexity: O(log n) where n is the length of nums
• Space Complexity: O(1)

Problem 3: Search in Rotated Sorted Array

Problem Statement

There is an integer array nums sorted in ascending order (with distinct values).

Prior to being passed to your function, nums is possibly rotated at an unknown pivot index k (1 <= k < nums.length) such that the resulting array is [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]] (0-indexed).

Given the array nums after the possible rotation and an integer target, return the index of target if it is in nums, or -1 if it is not in nums.

You must write an algorithm with O(log n) runtime complexity.

Example

Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4

Understanding the Problem

We need to search for a target in a rotated sorted array. The challenge is determining which half of the array to search, since the array is rotated.

Solution Strategy

Binary Search with Rotation Handling:

1. Determine which half is sorted by comparing nums[mid] with nums[right]
2. If left half is sorted:
   • If target is in range [nums[left], nums[mid]], search left
   • Otherwise, search right
3. If right half is sorted:
   • If target is in range [nums[mid], nums[right]], search right
   • Otherwise, search left

C# Solution

public class Solution 
{
    public int Search(int[] nums, int target) 
    {
        int left = 0, right = nums.Length - 1;
        
        while (left < right)
        {
            int mid = left + (right - left) / 2;
            
            // Determine which half is sorted
            if (nums[mid] > nums[right])
            {
                // Left half is sorted
                if (target > nums[mid] || target <= nums[right])
                {
                    // Target is in right half
                    left = mid + 1;
                }
                else
                {
                    // Target is in left half
                    right = mid;
                }
            }
            else
            {
                // Right half is sorted
                if (target > nums[mid] && target <= nums[right])
                {
                    // Target is in right half
                    left = mid + 1;
                }
                else
                {
                    // Target is in left half
                    right = mid;
                }
            }
        }
        
        // Check if target was found
        if (left == right && nums[left] == target)
            return left;
        
        return -1;
    }
}

Python 3 Solution

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        left = 0
        right = len(nums) - 1
        
        while left < right:
            middle = left + (right - left) // 2
            
            if nums[middle] > nums[right]:
                # Left half is sorted
                if target > nums[middle] or target <= nums[right]:
                    left = middle + 1
                else:
                    right = middle
            else:
                # Right half is sorted
                if target > nums[middle] and target <= nums[right]:
                    left = middle + 1
                else:
                    right = middle
        
        if left == right and nums[left] == target:
            return left
        
        return -1

Complexity Analysis

• Time Complexity: O(log n) where n is the length of nums
• Space Complexity: O(1)

Problem 4: Capacity To Ship Packages Within D Days

Problem Statement

A conveyor belt has packages that must be shipped from one port to another within days days.

The ith package on the conveyor belt has a weight of weights[i]. Each day, we load the ship with packages on the conveyor belt (in the order given by weights). We may not load more weight than the maximum weight capacity of the ship.

Return the least weight capacity of the ship that will result in all the packages on the conveyor belt being shipped within days days.

Example

Input: weights = [1,2,3,4,5,6,7,8,9,10], days = 5
Output: 15
Explanation: A ship capacity of 15 is the minimum to ship all the packages in 5 days like this:
1st day: 1, 2, 3, 4, 5
2nd day: 6, 7
3rd day: 8
4th day: 9
5th day: 10

Understanding the Problem

This is a binary search on answer problem. We’re not searching for an element in an array, but searching for the minimum capacity that satisfies the constraint.

Solution Strategy

Binary Search on Answer:

1. Search Space: Minimum capacity is max(weights) (must carry heaviest package), maximum is sum(weights) (carry all in one day)
2. Validation Function: For a given capacity, simulate loading packages and count days needed
3. Binary Search: If days needed > days, increase capacity; otherwise, try smaller capacity
4. Return the minimum valid capacity

C# Solution

public class Solution 
{
    public int ShipWithinDays(int[] weights, int days) 
    {
        // Minimum capacity: must carry heaviest package
        int left = weights.Max();
        // Maximum capacity: carry all packages in one day
        int right = weights.Sum();
        
        while (left < right)
        {
            int mid = left + (right - left) / 2;
            
            // Simulate loading with current capacity
            int currentCapacity = 0;
            int shipsNeeded = 1;
            
            foreach (int weight in weights)
            {
                currentCapacity += weight;
                
                // If exceeds capacity, need another ship
                if (currentCapacity > mid)
                {
                    currentCapacity = weight;
                    shipsNeeded++;
                }
            }
            
            // If we need more ships than available days, increase capacity
            if (shipsNeeded > days)
            {
                left = mid + 1;
            }
            else
            {
                // Try smaller capacity
                right = mid;
            }
        }
        
        return left;
    }
}

Python 3 Solution

class Solution:
    def shipWithinDays(self, weights: List[int], days: int) -> int:
        left = max(weights)
        right = sum(weights)
        
        while left < right:
            middle = left + (right - left) // 2
            
            currentCapacity = 0
            shipsNeeded = 1
            
            for weight in weights:
                currentCapacity += weight
                
                if currentCapacity > middle:
                    currentCapacity = weight
                    shipsNeeded += 1
            
            if shipsNeeded > days:
                left = middle + 1
            else:
                right = middle
        
        return left

Complexity Analysis

• Time Complexity: O(n × log(sum(weights))) where n is the number of packages
  • Binary search: O(log(sum(weights)))
  • Validation: O(n) for each search
• Space Complexity: O(1)

Key Takeaways

Binary Search Patterns:

1. Standard Binary Search

• Search for exact target in sorted array
• Template: left <= right, return index or -1

2. Binary Search for Insertion Position

• Find where to insert element
• Template: left < right, return left

3. Binary Search on Rotated Array

• Handle rotation by comparing with boundaries
• Determine which half is sorted first

4. Binary Search on Answer

• Search for optimal value that satisfies condition
• Requires validation function
• Common in optimization problems

Common Binary Search Techniques:

Avoiding Integer Overflow:

int mid = left + (right - left) / 2;  // ✅ Correct
int mid = (left + right) / 2;         // ❌ May overflow

Boundary Conditions:

• left <= right: Inclusive boundaries, standard search
• left < right: Exclusive right boundary, insertion position
• right = mid vs right = mid - 1: Depends on problem

Search Space Reduction:

• Always eliminate at least one element per iteration
• Ensure search space shrinks: left = mid + 1 or right = mid - 1

When to Use Binary Search:

• Sorted Array: Array must be sorted (or can be sorted)
• Search Problem: Finding element, position, or optimal value
• Optimization: Finding minimum/maximum that satisfies condition
• O(log n) Requirement: When O(log n) time complexity is needed

Problem-Solving Steps:

1. Identify Search Space: What are we searching for? (element, position, value)
2. Define Boundaries: What are the min and max possible values?
3. Write Validation: How do we check if a value is valid? (for binary search on answer)
4. Choose Template: Standard search, insertion, or rotated array?
5. Handle Edge Cases: Empty array, single element, not found

Common Mistakes:

• Integer Overflow: Using (left + right) / 2 instead of left + (right - left) / 2
• Infinite Loop: Not updating boundaries correctly
• Off-by-One Errors: Wrong boundary conditions
• Missing Edge Cases: Not handling empty arrays or single elements

Conclusion

Binary Search is a powerful algorithm that provides O(log n) time complexity for search problems. The key is recognizing when a problem can be solved with binary search and choosing the right template.

Key patterns to remember:

• Standard Search: Find exact element in sorted array
• Insertion Position: Find where to insert element
• Rotated Array: Handle rotation by comparing with boundaries
• Search on Answer: Find optimal value that satisfies condition

Practice identifying binary search opportunities and mastering the different templates. The more you practice, the better you’ll become at recognizing when and how to apply binary search.

Remember: Binary search requires a sorted array (or sortable problem space) and works by repeatedly dividing the search space in half. Always ensure your boundaries are updated correctly to avoid infinite loops.

Happy coding!