🚀 Day 9: Modified Binary Search Pattern (Amazon Interview Series)

Amazon frequently twists binary search into problems where arrays are rotated, infinite, or follow some special property.
Your ability to adapt the template is key.

---

🔑 Where Amazon Uses This Pattern

• Rotated sorted arrays (e.g., Amazon product listings with time-based rotation)
• Peak/mountain problems (finding optimal price point, peak traffic, etc.)
• Unknown-size arrays / infinite streams
• Search in bitonic arrays (increasing then decreasing sequences)
• Square root / first bad version problems

---

📝 Problem 1: Search in Rotated Sorted Array

👉 Amazon-style phrasing:
An array is rotated at some pivot. Search for target in O(log n).

Java Solution

public class RotatedArraySearch {
    public static int search(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;

            // Left half sorted
            if (nums[low] <= nums[mid]) {
                if (nums[low] <= target && target < nums[mid]) {
                    high = mid - 1;
                } else {
                    low = mid + 1;
                }
            }
            // Right half sorted
            else {
                if (nums[mid] < target && target <= nums[high]) {
                    low = mid + 1;
                } else {
                    high = mid - 1;
                }
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        int[] nums = {4,5,6,7,0,1,2};
        System.out.println(search(nums, 0)); // Output: 4
    }
}

✅ Pattern: Identify sorted half → discard accordingly.

---

📝 Problem 2: Find Minimum in Rotated Sorted Array

👉 Amazon-style phrasing:
Find the minimum element in a rotated sorted array.

Java Solution

public class FindMinRotated {
    public static 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;
            else high = mid;
        }
        return nums[low];
    }

    public static void main(String[] args) {
        int[] nums = {3,4,5,1,2};
        System.out.println(findMin(nums)); // Output: 1
    }
}

✅ Amazon hint: Pivot point = smallest element.

---

📝 Problem 3: Peak Element (Find Any Peak)

👉 Amazon-style phrasing:
A peak is an element greater than its neighbors. Find any peak in O(log n).

Java Solution

public class PeakElement {
    public static 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]) low = mid + 1;
            else high = mid;
        }
        return low;
    }

    public static void main(String[] args) {
        int[] nums = {1,2,1,3,5,6,4};
        System.out.println(findPeakElement(nums)); // Output: 1 or 5
    }
}

✅ Use case: Amazon might wrap this into "find the day with max orders".

---

📝 Problem 4: Search in Mountain Array

👉 Amazon-style phrasing:
A mountain array increases then decreases. Find target.

Java Solution

public class MountainArraySearch {
    private static int orderAgnosticBS(int[] arr, int target, int low, int high, boolean asc) {
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (arr[mid] == target) return mid;
            if (asc) {
                if (target < arr[mid]) high = mid - 1;
                else low = mid + 1;
            } else {
                if (target > arr[mid]) high = mid - 1;
                else low = mid + 1;
            }
        }
        return -1;
    }

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

        // find peak
        while (low < high) {
            int mid = low + (high - low) / 2;
            if (arr[mid] < arr[mid + 1]) low = mid + 1;
            else high = mid;
        }
        int peak = low;

        int left = orderAgnosticBS(arr, target, 0, peak, true);
        if (left != -1) return left;

        return orderAgnosticBS(arr, target, peak + 1, arr.length - 1, false);
    }

    public static void main(String[] args) {
        int[] arr = {1,3,5,7,6,4,2};
        System.out.println(searchInMountain(arr, 6)); // Output: 4
    }
}

✅ Amazon twist: Delivery efficiency (rise then fall pattern in orders).

---

📝 Problem 5: Search in Infinite Sorted Array

👉 Amazon-style phrasing:
You have an infinite sorted array (or ArrayReader API). Find the position of target.

Java Solution

public class InfiniteArraySearch {
    public static int searchInfinite(int[] arr, int target) {
        int low = 0, high = 1;

        // expand until target <= arr[high]
        while (high < arr.length && target > arr[high]) {
            low = high;
            high = high * 2;
            if (high >= arr.length) high = arr.length - 1;
        }

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

    public static void main(String[] args) {
        int[] arr = {3,5,7,9,10,90,100,130,140,160,170};
        System.out.println(searchInfinite(arr, 10)); // Output: 4
    }
}

✅ Amazon use: Searching logs or product lists that stream infinitely.

---

📚 Extended Problem List (Amazon Binary Search Twist Bank)

1. First Bad Version (find min index condition becomes true)
2. Kth Smallest Element in Sorted Matrix
3. Median of Two Sorted Arrays
4. Split Array Largest Sum (binary search on answer)
5. Capacity to Ship Packages within D Days (binary search on feasible capacity)

---

🎯 Key Takeaways

• Modified binary search works on sorted halves, conditions, or ranges.
• Think “how to discard half search space” → always the crux.
• Amazon wants you to explain edge cases (duplicates, infinite expansion, peak boundaries).

---

📅 Next in the series (Day 10):
👉 Two Heaps Pattern – Amazon favorites like “Median from Data Stream”, “IPO problem”, “Find Max Capital Projects”.

---