🔎 Day 11: Modified Binary Search – Amazon Interview Series

Binary Search is simple. But Amazon rarely asks vanilla binary search.
Instead, they twist it with rotations, conditions, peaks, or boundaries.

👉 This pattern helps solve:

• Rotated sorted arrays
• Find element in infinite arrays
• Peak / Mountain array problems
• First/Last occurrence of element

---

📝 Problem 1: Search in Rotated Sorted Array

👉 Amazon-style phrasing:
Given a rotated sorted array, return the index of target if found, else -1.

Java Solution

public class SearchRotatedArray {
    public static 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;

            if (nums[left] <= nums[mid]) { // left half sorted
                if (target >= nums[left] && target < nums[mid]) {
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            } else { // right half sorted
                if (target > nums[mid] && target <= nums[right]) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
        }
        return -1;
    }
}

✅ Time Complexity: O(log n)
✅ Amazon Insight: Always test if the half is sorted to decide where to go.

---

📝 Problem 2: Find Minimum in Rotated Sorted Array

👉 Amazon-style phrasing:
Given a rotated sorted array, find the minimum element.

Java Solution

public class FindMinRotated {
    public static 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; // min on right side
            } else {
                right = mid; // min on left including mid
            }
        }
        return nums[left];
    }
}

✅ Amazon Insight:
Tests your ability to adapt binary search without a target.

---

📝 Problem 3: Peak Element (Find Local Maximum)

👉 Amazon-style phrasing:
Find a peak element in the array. A peak is greater than its neighbors.

Java Solution

public class PeakElement {
    public static int findPeakElement(int[] nums) {
        int left = 0, right = nums.length - 1;

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

            if (nums[mid] < nums[mid + 1]) {
                left = mid + 1; // go right
            } else {
                right = mid; // go left (mid might be peak)
            }
        }
        return left;
    }
}

✅ Amazon Insight:
Binary Search applied even when array isn’t sorted.

---

📝 Problem 4: Find Element in Infinite Sorted Array

👉 Amazon-style phrasing:
You have an infinite sorted array. Find the position of target.

⚡ Trick:

• Expand range exponentially (1, 2, 4, 8...)
• Then apply binary search.

Java Solution

public class InfiniteArraySearch {
    public static int searchInfiniteArray(int[] nums, int target) {
        int left = 0, right = 1;

        while (right < nums.length && nums[right] < target) {
            left = right;
            right *= 2; // expand window
            if (right >= nums.length) right = nums.length - 1;
        }

        return binarySearch(nums, left, right, target);
    }

    private static int binarySearch(int[] nums, int left, int right, int target) {
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) return mid;
            if (nums[mid] < target) left = mid + 1;
            else right = mid - 1;
        }
        return -1;
    }
}

✅ Amazon Insight:
Tests scalability thinking — how to search without knowing the array size.

---

📝 Problem 5: First and Last Position of Element

👉 Amazon-style phrasing:
Find the first and last position of target in sorted array.

Java Solution

public class FirstLastPosition {
    public static int[] searchRange(int[] nums, int target) {
        return new int[]{findBound(nums, target, true), findBound(nums, target, false)};
    }

    private static int findBound(int[] nums, int target, boolean isFirst) {
        int left = 0, right = nums.length - 1, result = -1;

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

            if (nums[mid] == target) {
                result = mid;
                if (isFirst) right = mid - 1;
                else left = mid + 1;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return result;
    }
}

✅ Amazon Insight:
Tests how well you adapt binary search to find boundaries.

---

📚 Extended Problem List (Amazon Variations)

1. Search in Rotated Sorted Array II (with duplicates)
2. Find Peak in Mountain Array (LeetCode 1095 – Amazon loves this)
3. Square Root using Binary Search
4. Allocate Minimum Pages / Split Array Largest Sum (binary search on answer)
5. Aggressive Cows / Capacity to Ship Packages

---

🎯 Key Takeaways

• Modified Binary Search = framework adaptation.
• Always ask: What condition tells me which side to search?
• Variants: rotation, boundaries, infinite, peaks, binary search on answers.

---

📅 Next in the series (Day 12):
👉 Top-K Elements Pattern — heaps + priority queues, super important for Amazon.

---