← Back to Index

📚 Modified Binary Search Pattern – Java Cheat Sheet

📌 What Is It?

The Modified Binary Search Pattern involves solving problems where the search space is divided into halves to efficiently find a target or optimize a solution. This pattern is commonly used in sorted arrays or monotonic functions.

🧱 Pattern Templates

1️⃣ Standard Binary Search

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

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

            if (nums[mid] == target) {
                return mid; // Target found
            } else if (nums[mid] < target) {
                left = mid + 1; // Search right half
            } else {
                right = mid - 1; // Search left half
            }
        }

        return -1; // Target not found
    }
}

2️⃣ Binary Search in Rotated Sorted Array

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;

            if (nums[mid] == target) {
                return mid; // Target found
            }

            // Determine which half is sorted
            if (nums[left] <= nums[mid]) { // Left half is sorted
                if (nums[left] <= target && target < nums[mid]) {
                    right = mid - 1; // Search left half
                } else {
                    left = mid + 1; // Search right half
                }
            } else { // Right half is sorted
                if (nums[mid] < target && target <= nums[right]) {
                    left = mid + 1; // Search right half
                } else {
                    right = mid - 1; // Search left half
                }
            }
        }

        return -1; // Target not found
    }
}

3️⃣ Find Minimum in Rotated Sorted Array

class Solution {
    public int findMin(int[] nums) {
        int left = 0, right = nums.length - 1;

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

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

        return nums[left]; // Minimum element
    }
}

4️⃣ Peak Index in a Mountain Array

class Solution {
    public int peakIndexInMountainArray(int[] arr) {
        int left = 0, right = arr.length - 1;

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

            if (arr[mid] < arr[mid + 1]) {
                left = mid + 1; // Peak is in the right half
            } else {
                right = mid; // Peak is in the left half
            }
        }

        return left; // Peak index
    }
}

5️⃣ Binary Search on Monotonic Functions

class Solution {
    public int minimizeMax(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        int result = Integer.MAX_VALUE;

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

            if (isValid(nums, mid, target)) {
                result = mid; // Update result
                right = mid - 1; // Search left half
            } else {
                left = mid + 1; // Search right half
            }
        }

        return result;
    }

    private boolean isValid(int[] nums, int mid, int target) {
        // Custom logic to check if mid satisfies the condition
        return true;
    }
}

📊 Time Complexity

✅ Use Cases

📘 Common LeetCode Problems

🧪 Example: Binary Search

Input: nums = [-1,0,3,5,9,12], target = 9
Output: 4

Explanation:
- The target 9 is found at index 4.

💡 Pro Tips