Binary Search Patterns Series — Blog 1: Classic Binary Search & Variants

Binary search is the backbone of many DSA problems. Mastering it is critical for arrays, monotonic functions, matrices, and more advanced “search the answer” problems. In this first blog, we cover the classic patterns and variations.

1. Classic Binary Search (Iterative)

Problem: Search a target in a sorted array.

Template:

public int binarySearch(int[] arr, int target) {
    int low = 0, high = arr.length - 1;

    while (low <= high) {
        int mid = low + (high - low) / 2; // safe mid calculation

        if (arr[mid] == target) {
            return mid;
        } else if (arr[mid] < target) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    return -1; // target not found
}

Key Points:

mid = low + (high - low) / 2 avoids integer overflow.
low <= high ensures the last element is checked.
Returns -1 if target not found.

Example:

int[] arr = {1, 3, 5, 7, 9};
System.out.println(binarySearch(arr, 5)); // Output: 2
System.out.println(binarySearch(arr, 6)); // Output: -1

2. Recursive Binary Search

public int binarySearchRecursive(int[] arr, int low, int high, int target) {
    if (low > high) return -1;

    int mid = low + (high - low) / 2;
    if (arr[mid] == target) return mid;
    else if (arr[mid] < target) return binarySearchRecursive(arr, mid + 1, high, target);
    else return binarySearchRecursive(arr, low, mid - 1, target);
}

Example:

System.out.println(binarySearchRecursive(arr, 0, arr.length - 1, 7)); // Output: 3

3. Variants on Sorted Arrays

3.1 First Occurrence of Target (Duplicates Allowed)

public int firstOccurrence(int[] arr, int target) {
    int low = 0, high = arr.length - 1, ans = -1;

    while (low <= high) {
        int mid = low + (high - low) / 2;

        if (arr[mid] == target) {
            ans = mid;
            high = mid - 1; // search left half
        } else if (arr[mid] < target) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    return ans;
}

3.2 Last Occurrence of Target

public int lastOccurrence(int[] arr, int target) {
    int low = 0, high = arr.length - 1, ans = -1;

    while (low <= high) {
        int mid = low + (high - low) / 2;

        if (arr[mid] == target) {
            ans = mid;
            low = mid + 1; // search right half
        } else if (arr[mid] < target) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    return ans;
}

3.3 Count Occurrences

public int countOccurrences(int[] arr, int target) {
    int first = firstOccurrence(arr, target);
    if (first == -1) return 0;
    int last = lastOccurrence(arr, target);
    return last - first + 1;
}

3.4 Insert Position (Lower Bound)

public int searchInsertPosition(int[] arr, int target) {
    int low = 0, high = arr.length - 1;

    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (arr[mid] < target) low = mid + 1;
        else high = mid - 1;
    }
    return low; // position to insert target
}

Example:

int[] arr = {1,3,5,6};
System.out.println(searchInsertPosition(arr, 5)); // Output: 2
System.out.println(searchInsertPosition(arr, 2)); // Output: 1
System.out.println(searchInsertPosition(arr, 7)); // Output: 4