Binary Search Variations

Generated on 2025-07-10 02:06:58 Algorithm Cheatsheet for Technical Interviews

Binary Search Variations: Cheatsheet

1. Quick Overview

Binary Search is an efficient algorithm for finding a target value within a sorted array. It works by repeatedly dividing the search interval in half. Use it when:

You have a sorted array (or a condition that behaves like a sorted array).
You need to find an element quickly (logarithmic time).
You need to find the first/last occurrence of an element.
You need to find an element satisfying a certain condition (e.g., smallest element greater than a target).

2. Time & Space Complexity

Time Complexity: O(log n), where n is the size of the array.
Space Complexity: O(1) (iterative), O(log n) (recursive, due to call stack). Tail-call optimization can sometimes reduce recursive space complexity to O(1).

3. Implementation

Here’s a basic iterative binary search in Python, Java, and C++:

Python:

def binary_search(arr, target):
    """
    Performs binary search on a sorted array.
    Args:
        arr: The sorted array.
        target: The value to search for.
    Returns:
        The index of the target if found, otherwise -1.
    """
    left, right = 0, len(arr) - 1

    while left <= right:
        mid = left + (right - left) // 2  # Prevent potential overflow

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

    return -1

# Example Usage:
arr = [2, 5, 7, 8, 11, 12]
target = 13
result = binary_search(arr, target)

if result != -1:
    print(f"Element is present at index {result}")
else:
    print("Element is not present in array")

Java:

class BinarySearch {
    public static int binarySearch(int[] arr, int target) {
        int left = 0;
        int right = arr.length - 1;

        while (left <= right) {
            int mid = left + (right - left) / 2; // Prevent potential overflow

            if (arr[mid] == target) {
                return mid;
            } else if (arr[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        return -1;
    }

    public static void main(String[] args) {
        int[] arr = {2, 5, 7, 8, 11, 12};
        int target = 13;
        int result = binarySearch(arr, target);

        if (result != -1) {
            System.out.println("Element is present at index " + result);
        } else {
            System.out.println("Element is not present in array");
        }
    }
}

C++:

#include <iostream>
#include <vector>

int binarySearch(const std::vector<int>& arr, int target) {
    int left = 0;
    int right = arr.size() - 1;

    while (left <= right) {
        int mid = left + (right - left) / 2; // Prevent potential overflow

        if (arr[mid] == target) {
            return mid;
        } else if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }

    return -1;
}

int main() {
    std::vector<int> arr = {2, 5, 7, 8, 11, 12};
    int target = 13;
    int result = binarySearch(arr, target);

    if (result != -1) {
        std::cout << "Element is present at index " << result << std::endl;
    } else {
        std::cout << "Element is not present in array" << std::endl;
    }

    return 0;
}

4. Common Patterns

| Find Last Occurrence | Find the index of the last occurrence of a target value. | last_occurrence(arr, target) a little bit of the same.

Find Boundary: Find the first element that satisfies a condition (e.g., first element >= target).
Find Inflection Point: Find a “peak” or “valley” in a unimodal array.
Allocate Minimum: Binary search on the answer (search space is a range of possible values).
Search in Rotated Sorted Array: Find the index of a target in a rotated sorted array.

Python - Find First Occurrence:

def first_occurrence(arr, target):
    """
    Finds the index of the first occurrence of a target in a sorted array.
    Args:
        arr: The sorted array.
        target: The value to search for.
    Returns:
        The index of the first occurrence if found, otherwise -1.
    """
    left, right = 0, len(arr) - 1
    result = -1  # Initialize to -1 to handle cases where target is not found

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

        if arr[mid] == target:
            result = mid  # Found a match, but keep searching to the left
            right = mid - 1  # Move right pointer to the left to potentially find an earlier occurrence
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1

    return result

Python - Find Last Occurrence:

def last_occurrence(arr, target):
    """
    Finds the index of the last occurrence of a target in a sorted array.
    Args:
        arr: The sorted array.
        target: The value to search for.
    Returns:
        The index of the last occurrence if found, otherwise -1.
    """
    left, right = 0, len(arr) - 1
    result = -1

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

        if arr[mid] == target:
            result = mid  # Found a match, but keep searching to the right
            left = mid + 1  # Move left pointer to the right to potentially find a later occurrence
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1

    return result

Python - Find Boundary:

def find_boundary(arr, condition