Binary Search Algorithm Implementation and Applications

Binary search is a fundamental divide-and-conquer algorithm that efficiently finds elements in sorted arrays or determines boundaries in sorted data, making it essential for FAANG technical interviews and real-world applications.

1. Pattern Restatement

Clarifying questions to ask the interviewer:

1. What are the constraints on input size? Are we dealing with arrays up to 10⁶ elements, or potentially larger?
2. Are duplicates allowed in the input array? This affects how we handle boundary conditions and whether we can use certain optimizations.
3. What is the expected return format? Should I return an index, boolean, or a specific value from the array?
4. Can I mutate the input array? Some binary search problems require maintaining original order.
5. What is the target complexity for follow-ups? Is O(n) acceptable, or should I aim for O(log n)?

Restatement of the pattern:

Binary search is a divide-and-conquer algorithm that efficiently finds a target value in a sorted array by repeatedly dividing the search space in half. It operates on the principle that if we can determine whether the target lies in the left or right half of the current search space, we can eliminate half of the remaining elements at each step.

Signal words and constraint shape:

• Sorted input or sorted array: The most critical signal, as binary search only works on sorted data.
• "Find the target" or "locate a value": Indicating search rather than computation.
• "Minimum/maximum element" or "first/last occurrence": Often solved with binary search variants.
• "At most k elements" or "at least k elements": These often suggest binary search on the answer space.
• Large input size: When O(n) is too slow, binary search offers O(log n) performance.

Assumptions:

• The input array is sorted in ascending order (or can be made so).
• The target value exists or we are searching for a boundary condition.
• We can access elements by index in O(1) time.

Scenario suitability:

This pattern is best suited for static scenarios where the input data is fixed and we're performing multiple searches or optimizations. It's less suitable for streaming data where the array keeps changing, as we'd need to re-sort or rebuild the search structure. For online scenarios with frequent updates, a different approach like a self-balancing tree or segment tree would be more appropriate.

The pattern excels in problems where we can make a monotonic decision: if we know that elements to the left of a certain point don't satisfy our condition, we can safely ignore them. This property makes binary search ideal for optimization problems and searching in sorted collections.

2. When to Use This Pattern

Signal words and constraint shapes in a problem statement that indicate this pattern:

• "Search for a target value" or "find the position of an element"
• "Sorted array" or "sorted input"
• "Optimize for time complexity" with O(log n) target
• "Find the first/last occurrence" or "find insertion point"
• "Range queries" or "find element within bounds"

Why this pattern fits better than the most common alternatives: Binary search is optimal for sorted data where we can eliminate half the search space at each step. Compared to linear search (O(n)), it provides logarithmic time complexity. Unlike hash-based approaches, it works directly on sorted arrays without requiring additional space for indexing structures.

Conditions where a variation or related pattern applies instead:

• Two pointers: When we need to find pairs or triplets that sum to a target in a sorted array, two pointers can be more intuitive than binary search
• Sliding window: For problems involving subarrays with specific constraints, sliding window might be more appropriate when the constraint is about ranges rather than exact matches
• Ternary search: When we're searching for the minimum or maximum of a unimodal function, ternary search can be more efficient than binary search

The core insight that makes this pattern work: The fundamental insight is that in sorted data, we can make deterministic decisions about which half of the array contains our target. If the middle element is greater than our target, we know the target must be in the left half; if it's less, it must be in the right half. This property enables us to eliminate half of the remaining search space at each iteration.

This pattern is particularly powerful because it transforms a linear search problem into a logarithmic one, making it ideal for large datasets where performance is critical.

3. Approach Evolution

Interview communication script:

"My first instinct is to solve this with linear search, checking each element one by one. But that's O(n) time complexity because in the worst case, I'd have to look at every element. That's not efficient for large datasets.

Let me think about how to optimize this. I notice that if the array is sorted, I can take advantage of that ordering property. Instead of scanning sequentially, I can use binary search to eliminate half the remaining elements at each step.

I'm looking for a specific target value in a sorted array. The key insight is that since the array is sorted, if I look at the middle element and compare it to my target, I can determine whether the target lies in the left half or right half. This is the fundamental invariant that makes binary search work.

If I maintain the invariant that my search space is always sorted, I can reduce the problem size by half at each step. This leads to O(log n) time complexity instead of O(n). The algorithm terminates when the target is found or when the search space becomes empty."

Brute-force approach:

• Linear scan through entire array
• Time complexity: O(n)
• Space complexity: O(1)
• Not ideal because it ignores the sorted property of input

Improved approach:

• Binary search leveraging sorted nature
• Time complexity: O(log n)
• Space complexity: O(1) for iterative, O(log n) for recursive
• Key optimization: At each step, eliminate half the remaining search space

Final approach with step-by-step reasoning:

1. Start with left = 0 and right = array.length - 1
2. While left ≤ right:
   • Calculate mid = (left + right) / 2
   • If nums[mid] == target: return mid
   • If nums[mid] < target: search right half (left = mid + 1)
   • If nums[mid] > target: search left half (right = mid - 1)
3. Return -1 if not found

Important invariants that must hold:

• Search space boundaries always maintain sorted property
• Left pointer never exceeds right pointer during iteration
• At each step, we're eliminating half the remaining elements
• Loop condition ensures we don't miss any valid search space

4. Data Structure Choice

The primary data structure used is a sorted array or sorted list, which enables the binary search algorithm to function by allowing O(1) access to elements at any index.

Why Sorted Array is Needed

The sorted array is fundamental because binary search relies on the ability to compare a target value with the middle element and eliminate half of the remaining search space. Without sorted order, we cannot make meaningful comparisons to guide our search.

Time and Space Impact

• Time Complexity: O(1) for element access, O(log n) for search operations
• Space Complexity: O(1) additional space for the search variables (left, right, mid pointers)

Helper Structures

No additional helper structures are required for basic binary search implementation. The algorithm operates directly on the input array using three integer pointers:

• left pointer to track the start of search range
• right pointer to track the end of search range
• mid pointer to calculate the middle position

The simplicity of using only three integer pointers makes this approach highly efficient in both time and space, avoiding the overhead of more complex data structures like hash tables or trees.

Why This Choice is Optimal

This choice directly leverages the sorted property of the input data, making it the most efficient approach for searching in a sorted collection. Any alternative requiring additional data structures would either increase space complexity or lose the benefits of the sorted arrangement that makes binary search possible.

5. Algorithm Walkthrough

Let me trace through the binary search algorithm using the example where we're searching for target = 7 in array [1, 3, 5, 7, 9, 11, 13].

Step 1: Initialize pointers - left = 0, right = 6

• Array: [1, 3, 5, 7, 9, 11, 13]
• Mid = (0 + 6) / 2 = 3
• Element at mid = 7, which equals our target

Step 2: Return immediately since we found the target at index 3

• No further iterations needed

Let me trace a more complex case where target = 9:

Step 1: Initialize pointers - left = 0, right = 6

• Array: [1, 3, 5, 7, 9, 11, 13]
• Mid = (0 + 6) / 2 = 3
• Element at mid = 7, which is less than target 9
• Move left pointer to mid + 1 = 4

Step 2: left = 4, right = 6

• Mid = (4 + 6) / 2 = 5
• Element at mid = 11, which is greater than target 9
• Move right pointer to mid - 1 = 4

Step 3: left = 4, right = 4

• Mid = (4 + 4) / 2 = 4
• Element at mid = 9, which equals our target
• Return index 4

Edge case handling: When array is empty, left > right immediately, return -1 When target < all elements, right keeps moving left until left > right When target > all elements, left keeps moving right until left > right

The algorithm terminates correctly because we always maintain the invariant that target, if present, must be in the current [left, right] range.

6. Java Solution

public class BinarySearchSolution {
    
    /**
     * Standard binary search on a sorted array
     * Returns index of target if found, otherwise -1
     */
    public int search(int[] nums, int target) {
        if (nums == null || nums.length == 0) {
            return -1;
        }
        
        int left = 0;
        int right = nums.length - 1;
        
        while (left <= right) {
            // Prevent integer overflow by using this instead of (left + right) / 2
            int mid = left + (right - left) / 2;
            
            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] < target) {
                left = mid + 1;  // Search right half
            } else {
                right = mid - 1; // Search left half
            }
        }
        
        return -1; // Target not found
    }
    
    /**
     * Find the first occurrence of target in a sorted array with duplicates
     */
    public int findFirst(int[] nums, int target) {
        if (nums == null || nums.length == 0) {
            return -1;
        }
        
        int left = 0;
        int right = nums.length - 1;
        int result = -1;
        
        while (left <= right) {
            int mid = left + (right - left) / 2;
            
            if (nums[mid] == target) {
                result = mid;        // Record occurrence
                right = mid - 1;     // Continue searching left half
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        
        return result;
    }
    
    /**
     * Find the last occurrence of target in a sorted array with duplicates
     */
    public int findLast(int[] nums, int target) {
        if (nums == null || nums.length == 0) {
            return -1;
        }
        
        int left = 0;
        int right = nums.length - 1;
        int result = -1;
        
        while (left <= right) {
            int mid = left + (right - left) / 2;
            
            if (nums[mid] == target) {
                result = mid;        // Record occurrence
                left = mid + 1;      // Continue searching right half
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        
        return result;
    }
    
    /**
     * Search in rotated sorted array (with duplicates)
     * Handles cases where nums[left] == nums[mid] == nums[right]
     */
    public boolean searchRotated(int[] nums, int target) {
        if (nums == null || nums.length == 0) {
            return false;
        }
        
        int left = 0;
        int right = nums.length - 1;
        
        while (left <= right) {
            int mid = left + (right - left) / 2;
            
            if (nums[mid] == target) {
                return true;
            }
            
            // Handle duplicates: when nums[left] == nums[mid] == nums[right]
            if (nums[left] == nums[mid] && nums[mid] == nums[right]) {
                left++;
                right--;
            } else if (nums[left] <= nums[mid]) {
                // Left half is sorted
                if (nums[left] <= target && target < nums[mid]) {
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            } else {
                // Right half is sorted
                if (nums[mid] < target && target <= nums[right]) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
        }
        
        return false;
    }
}

7. Complexity Analysis

Time Complexity: O(log n)

The algorithm performs binary search on the array, which halves the search space at each step. Since we divide the array size by 2 in each iteration, the maximum number of operations required is ⌊log₂(n)⌋ + 1. Each iteration involves constant-time operations (comparisons and index calculations), so the overall time complexity is O(log n).

Space Complexity: O(1)

The solution uses only a constant amount of extra space for variables left, right, and mid. No additional data structures grow with input size, making the space complexity O(1). This is optimal for an iterative binary search implementation.

Why These Bounds Are Correct:

The logarithmic time complexity stems from the fundamental property of binary search: at each step, we eliminate half of the remaining elements. Starting with n elements, after one comparison we have n/2 elements, then n/4, and so on until we find the target or exhaust the search space. This follows the mathematical property that log₂(n) represents how many times we can divide n by 2 before reaching 1.

The constant space complexity is guaranteed because:

1. We only use a fixed number of integer variables (left, right, mid)
2. No recursive call stack is created
3. No auxiliary data structures are built or maintained

This complexity bound is optimal for the problem since any comparison-based search algorithm must examine at least log₂(n) elements in the worst case to guarantee finding a target element, making our solution asymptotically optimal.

8. Edge Cases & Pitfalls

Empty and Minimal Inputs

• Empty array: Binary search on an empty array should return -1 (or appropriate sentinel value) to indicate "not found"
• Single element: Must handle arrays of size 1 correctly - the search key should match the only element or return not found
• Two elements: Careful with mid calculation to avoid infinite loops

Duplicate Values and Repeated States

• Duplicate elements: Standard binary search works with duplicates, but if the problem asks for first/last occurrence, special handling is needed
• Multiple matches: When searching for a target value that appears multiple times, the algorithm may return any valid index
• Array with all same elements: Could cause issues with improper boundary updates in some implementations

Boundary Conditions

• Integer overflow: When calculating mid = (left + right) / 2, use mid = left + (right - left) / 2 to prevent overflow
• Left/right boundary updates: Incorrectly updating left = mid instead of left = mid + 1 can cause infinite loops
• Right boundary: Setting right = mid - 1 when it should be right = mid can skip valid elements

Common Implementation Mistakes

• Infinite loop: Using left = mid and right = mid without proper boundary adjustments
• Off-by-one errors: Incorrectly handling the case where left == right and not updating boundaries
• Wrong condition checks: Using <= instead of < in loop conditions, or incorrect comparison operators
• Incorrect mid calculation: Not accounting for integer overflow when computing mid
• Not handling search space properly: Failing to correctly shrink the search space in each iteration

// Example of problematic code:
// This can cause infinite loop:
// while (left <= right) {
//     int mid = (left + right) / 2; // Potential overflow
//     if (arr[mid] == target) return mid;
//     else if (arr[mid] < target) left = mid; // Should be mid + 1
//     else right = mid; // Should be mid - 1
// }

9. Alternative Approaches

There are several alternative approaches to solving problems that might seem like they could use binary search, though each has different trade-offs:

Linear Search: For small input sizes (n < 100), a simple linear search might be preferable due to lower constant factors and simpler implementation. This approach has O(n) time complexity but no overhead from binary search logic.

Interpolation Search: When the input array is uniformly distributed, interpolation search can achieve O(log log n) average time complexity by estimating the position of the target element. However, it requires uniform distribution and has O(n) worst-case complexity.

Exponential Search: Useful when the search space is unbounded or when we don't know the upper bound. It first finds a range where the target might exist in O(log i) time, then performs binary search in that range. This is particularly useful for finding the first occurrence of a target in an infinite stream.

Ternary Search: Divides the search space into three parts instead of two. While it theoretically reduces the search space faster, it actually has higher constant factors and is rarely preferred over binary search in practice.

Hash-based approaches: For problems where we need to perform multiple lookups, building a hash map first (O(n) preprocessing) followed by O(1) lookups can be more efficient than repeated binary searches, especially when the number of queries is large.

The chosen binary search approach is optimal for problems where we have a sorted array and need to find a specific element or property, particularly when the input size is large enough that the O(log n) complexity provides significant benefit over linear approaches.

10. Test Cases

public class TestCases {
    public static void main(String[] args) {
        // Test case 1: Basic example from problem description
        int[] nums1 = {4, 5, 6, 7, 0, 1, 2};
        int target1 = 0;
        // Expected: 4
        
        // Test case 2: Target not found
        int[] nums2 = {4, 5, 6, 7, 0, 1, 2};
        int target2 = 3;
        // Expected: -1
        
        // Test case 3: Array with no rotation (sorted array)
        int[] nums3 = {1, 2, 3, 4, 5};
        int target3 = 3;
        // Expected: 2
        
        // Test case 4: Single element array
        int[] nums4 = {5};
        int target4 = 5;
        // Expected: 0
        
        // Test case 5: Single element array, target not found
        int[] nums5 = {5};
        int target5 = 3;
        // Expected: -1
        
        // Test case 6: Two elements, target found
        int[] nums6 = {2, 1};
        int target6 = 2;
        // Expected: 0
        
        // Test case 7: Two elements, target not found
        int[] nums7 = {2, 1};
        int target7 = 3;
        // Expected: -1
        
        // Test case 8: Large rotation point
        int[] nums8 = {5, 1, 2, 3, 4};
        int target8 = 1;
        // Expected: 1
        
        // Test case 9: All same elements
        int[] nums9 = {3, 3, 3, 3, 3};
        int target9 = 3;
        // Expected: 0 (or any valid index)
        
        // Test case 10: Empty array
        int[] nums10 = {};
        int target10 = 1;
        // Expected: -1
    }
}

Sample test cases include:

• Basic rotated sorted array with found target (index 4)
• Target not present in the array (returns -1)
• Non-rotated sorted array (returns correct index)
• Edge cases with single and two-element arrays
• Arrays with duplicate elements
• Empty array edge case

The test cases cover typical scenarios including boundary conditions, duplicates, and various rotation points to ensure robustness of the binary search implementation.

11. Final Summary

The core idea is to leverage the sorted property of the input array to eliminate half of the remaining search space at each step, achieving logarithmic time complexity. This solution works because we can always determine which half contains our target value by comparing it with the middle element, making binary search optimal for sorted arrays. The efficiency comes from reducing the problem size by half with each comparison, resulting in O(log n) time complexity that's fundamentally better than linear search's O(n).