← Back to All Patterns

Modified Binary Search

Modified Binary Search Animation

Search for 1 in rotated sorted array
idx 0
4
L
idx 1
5
idx 2
6
idx 3
7
M
idx 4
0
idx 5
1
idx 6
2
R
Left Pointer
0
arr[0] = 4
Mid Pointer
3
arr[3] = 7
Right Pointer
6
arr[6] = 2

Start: Search for 1 in rotated sorted array

Speed:
Step 1 of 3

💡 Key Concept:

In a rotated sorted array, one half is always sorted. Identify which half is sorted, check if target is in that range, then decide to search left or right. Time: O(log n)

🎯 Explain Like I'm 5...

Imagine finding your favorite book 📚 on a shelf with 100 books in order... but OH NO! Someone spun the shelf and now it's twisted!

📖 The Smart Search (Binary Search):

  • • Normal shelf: Books 1,2,3,4,5,6,7 → Look at book in MIDDLE (4)
  • • Is your book bigger than 4? → Look in right half!
  • • Is your book smaller than 4? → Look in left half!
  • • Keep cutting in half until you find it! ✂️

🔄 Twisted shelf (Modified): Books are 4,5,6,7,1,2,3

  • • Look at middle (book 7)
  • • One half is STILL in order! Figure out which half!
  • • Check if your book is in the ordered half
  • • Cut that half in half again!

🚀 Why is it fast? Instead of checking ALL 100 books (slow! 😴), you cut the shelf in half each time! 100 → 50 → 25 → 12 → 6 → 3 → 1... Found in just 7 steps! 🎯

When Should You Use This Pattern?

  • ✓Array is sorted or partially sorted
  • ✓Finding elements in rotated sorted array
  • ✓Finding first/last occurrence of a target
  • ✓Need O(log n) time complexity

📝 Example 1: Search in Rotated Sorted Array

Search for a target in a rotated sorted array like [4,5,6,7,0,1,2].

Step-by-Step Thinking:

  1. Find mid point
  2. One half will always be sorted
  3. Check if target is in the sorted half
  4. If yes, search that half; if no, search the other half
RotatedSearch.java
java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
public class RotatedSearch {
    public static int search(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                return mid;
            }
            // Determine which half is sorted
            if (nums[left] <= nums[mid]) {
                // Left half is sorted
                if (target >= nums[left] && target < nums[mid]) {
                    right = mid - 1;  // Target in left half
                } else {
                    left = mid + 1;   // Target in right half
                }
            } else {
                // Right half is sorted
                if (target > nums[mid] && target <= nums[right]) {
                    left = mid + 1;   // Target in right half
                } else {
                    right = mid - 1;  // Target in left half
                }
            }
        }
        return -1;  // Not found
    }
    public static void main(String[] args) {
        int[] nums = {4, 5, 6, 7, 0, 1, 2};
        int target = 0;
        System.out.println("Index of " + target + ": " + search(nums, target));
        // Output: Index of 0: 4
        target = 3;
        System.out.println("Index of " + target + ": " + search(nums, target));
        // Output: Index of 3: -1
    }
}

📝 Example 2: Find First and Last Position

Find the starting and ending position of a target in a sorted array.

FindRange.java
java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
public class FindRange {
    public static int[] searchRange(int[] nums, int target) {
        int[] result = {-1, -1};
        // Find first occurrence
        result[0] = findBound(nums, target, true);
        // Only search for last if first was found
        if (result[0] != -1) {
            result[1] = findBound(nums, target, false);
        }
        return result;
    }
    private static int findBound(int[] nums, int target, boolean findFirst) {
        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;  // Found a match
                if (findFirst) {
                    right = mid - 1;  // Continue searching left for first
                } else {
                    left = mid + 1;   // Continue searching right for last
                }
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return result;
    }
    public static void main(String[] args) {
        int[] nums = {5, 7, 7, 8, 8, 10};
        int target = 8;
        int[] range = searchRange(nums, target);
        System.out.println("Range: [" + range[0] + ", " + range[1] + "]");
        // Output: Range: [3, 4]
        target = 6;
        range = searchRange(nums, target);
        System.out.println("Range: [" + range[0] + ", " + range[1] + "]");
        // Output: Range: [-1, -1]
    }
}

📝 Example 3: Search in Infinite Array

Find an element in a sorted array of unknown size (infinite array).

InfiniteArray.java
java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
class ArrayReader {
    int[] arr;
    ArrayReader(int[] arr) { this.arr = arr; }
    int get(int index) {
        if (index >= arr.length) return Integer.MAX_VALUE;
        return arr[index];
    }
}
public class InfiniteArray {
    public static int search(ArrayReader reader, int target) {
        // Step 1: Find the bounds where target could be
        int left = 0;
        int right = 1;
        // Expand bounds exponentially
        while (reader.get(right) < target) {
            left = right;
            right = right * 2;  // Double the search range
        }
        // Step 2: Binary search within the bounds
        return binarySearch(reader, target, left, right);
    }
    private static int binarySearch(ArrayReader reader, int target,
                                     int left, int right) {
        while (left <= right) {
            int mid = left + (right - left) / 2;
            int value = reader.get(mid);
            if (value == target) {
                return mid;
            } else if (value > target) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return -1;
    }
    public static void main(String[] args) {
        int[] arr = {1, 3, 8, 10, 15, 20, 30, 40, 50};
        ArrayReader reader = new ArrayReader(arr);
        int target = 15;
        System.out.println("Index of " + target + ": " + search(reader, target));
        // Output: Index of 15: 4
        target = 25;
        System.out.println("Index of " + target + ": " + search(reader, target));
        // Output: Index of 25: -1
    }
}

🔑 Key Points to Remember

  • 1️⃣Always use mid = left + (right - left) / 2 to avoid overflow
  • 2️⃣For rotated arrays, one half is always sorted
  • 3️⃣Time Complexity: O(log n) - halve search space each time
  • 4️⃣Space Complexity: O(1) - no extra space needed

💪 Practice Problems

  • • Find Minimum in Rotated Sorted Array
  • • Search in a 2D Matrix
  • • Find Peak Element
  • • Find Smallest Letter Greater Than Target
  • • Search Bitonic Array