🔍 Mastering the Binary Search Pattern (with Java Code Examples)

Binary Search is one of the most powerful techniques in computer science and is used to solve problems that involve searching, sorting, or finding a position within a sorted dataset.

Understanding the Binary Search Pattern is crucial for coding interviews, particularly at top tech companies like Google, Facebook, and Amazon. Binary search allows you to reduce the time complexity of many problems from O(n) to O(log n), making it an essential tool in your problem-solving toolkit.

📌 What Is Binary Search?

Binary Search is a divide and conquer algorithm used to search for a target value within a sorted array (or list). It works by repeatedly dividing the search interval in half and discarding half of the remaining elements at each step, until the target value is found or the interval is empty.

Steps for Binary Search:

1. Start with the entire array and set two pointers: one at the start (low) and one at the end (high).
2. Find the middle element of the array.
3. If the middle element equals the target, return the index.
4. If the target is smaller, set the high pointer to mid - 1 (focus on the left half).
5. If the target is larger, set the low pointer to mid + 1 (focus on the right half).
6. Repeat until the target is found or the pointers cross.

⚙️ Basic Binary Search Code

Here’s the simple implementation of the classic binary search to find a target in a sorted array.

Code Snippet: Binary Search (Iterative)

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

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

        if (nums[mid] == target) {
            return mid; // Target found
        } else if (nums[mid] < target) {
            low = mid + 1; // Target is in the right half
        } else {
            high = mid - 1; // Target is in the left half
        }
    }
    return -1; // Target not found
}

📊 Time Complexity

• Time Complexity: O(log n)
• Space Complexity: O(1) (for iterative) or O(log n) (for recursive due to stack calls)

🔍 Variants of Binary Search

Binary Search can be modified for different use cases. Here are some of the most common variations of Binary Search.

1. Finding the First Occurrence of a Target

Sometimes, the array can contain multiple instances of the target value, and we need to find the first occurrence. This can be achieved by modifying the binary search slightly.

Code Snippet: First Occurrence of Target

public int findFirst(int[] nums, int target) {
    int low = 0, high = nums.length - 1;
    int result = -1;

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

        if (nums[mid] == target) {
            result = mid; // Store the index and continue to search left
            high = mid - 1;
        } else if (nums[mid] < target) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }

    return result; // Returns the first occurrence index
}

2. Finding the Last Occurrence of a Target

Similar to the first occurrence, you can modify binary search to find the last occurrence of a target.

Code Snippet: Last Occurrence of Target

public int findLast(int[] nums, int target) {
    int low = 0, high = nums.length - 1;
    int result = -1;

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

        if (nums[mid] == target) {
            result = mid; // Store the index and continue to search right
            low = mid + 1;
        } else if (nums[mid] < target) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }

    return result; // Returns the last occurrence index
}

3. Finding the Insert Position

Another common problem is finding the insert position for a target in a sorted array. This helps you when you need to insert the target value and maintain the order.

Code Snippet: Insert Position

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

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

        if (nums[mid] == target) {
            return mid;
        } else if (nums[mid] < target) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }

    return low; // Insert position (low is where the target should be placed)
}

4. Finding the Smallest Element in a Rotated Sorted Array

Binary search can also be adapted to find the smallest element in a rotated sorted array. A rotated array is a sorted array that has been rotated at some pivot point.

Code Snippet: Find Minimum in Rotated Sorted Array

public int findMin(int[] nums) {
    int low = 0, high = nums.length - 1;

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

        if (nums[mid] > nums[high]) {
            low = mid + 1; // Minimum is on the right side
        } else {
            high = mid; // Minimum is on the left side
        }
    }

    return nums[low]; // low will point to the smallest element
}

5. Finding the Peak Element

In some problems, you might need to find a peak element. A peak is defined as an element that is strictly greater than its neighbors.

Code Snippet: Find Peak Element

public int findPeakElement(int[] nums) {
    int low = 0, high = nums.length - 1;

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

        if (nums[mid] > nums[mid + 1]) {
            high = mid; // Peak is in the left half
        } else {
            low = mid + 1; // Peak is in the right half
        }
    }

    return low; // Return index of peak element
}

6. Finding the Square Root (Integer Part)

Finding the integer square root of a number using binary search is a common problem. We need to find the largest integer x such that x^2 <= n.

Code Snippet: Find Integer Square Root

public int mySqrt(int x) {
    int low = 0, high = x;

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

        if (midSquare == x) {
            return mid;
        } else if (midSquare < x) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }

    return high; // high will be the integer part of sqrt(x)
}

🔄 Real-World Applications of Binary Search

• Searching: Quickly locating an element in a sorted dataset (e.g., looking up a word in a dictionary).
• Optimization problems: When searching for the optimal solution (e.g., maximum profit, minimum cost).
• Range Queries: For problems that involve querying ranges in a sorted list.
• Image processing: Searching for specific thresholds (e.g., finding a color or edge in an image).
• Version control: For identifying the earliest commit that caused a bug or problem.
• Game development: Searching for positions or elements in grids, maps, or sorted lists.

🧠 Interview Tips

• Always ensure the array is sorted (or can be sorted).
• Understand that binary search reduces the search space by half at each step, so make sure to adjust the pointers (low, high, mid) properly.
• Edge cases: Handle empty arrays, boundary values, and the case when the target isn't found.

💬 Practice Problems

✨ Final Words

Mastering the Binary Search pattern opens up a wide range of problems that can be solved efficiently. Once you become comfortable with the basic binary search technique, exploring its variations like finding the first/last occurrence, insert position, and peak elements will further enhance your problem-solving skills.

“If you can master Binary Search, you can solve a variety of problems with optimal performance.”