33.search-in-rotated-sorted-array.md

33. Search in Rotated Sorted Array

Hints

• What property does a rotated sorted array always have if there are no duplicates?
• Can you always find a sorted half if you split the array at the middle?
• How can you use this to reduce the search space with binary search?

Breakdowns

1. Can we use binary search directly on a rotated array?

No, but we can adapt it. At each step, at least one half of the array is sorted. We can use this to decide which half to search next.

2. How do we decide which half to search?

Check if the left or right half is sorted. If the target is in the sorted half, search there; otherwise, search the other half.

Key Insights

nums = [3, 4, 5, 6, 0, 1, 2]
        |--------|
                    |-----|
        L        M        R

There are two sorted parts in the rotated array: [3, 4, 5, 6] and [0, 1, 2]. For the pivot 6, all the right part [0, 1, 2] is less than the left part [3, 4, 5, 6]. We can use this property to find the target in the rotated array.

Does binary search work for rotated array? Here is some key observations, for [0, 1, 2, 3] with possible rotations:

 Left  Right  / Sorted?
[0, 1 | 2, 3]   Y, Y
[1, 2 | 3, 0]   Y, N
[2, 3 | 0, 1]   N, Y
[3, 0 | 1, 2]   Y, Y

As we split the array into two parts, at least one part is always sorted, so we can apply binary search to find the target in the sorted part, otherwise, we search another part. It still provides a way to predicatabily reduce the search space by half at each step. This's why binary search is still applicable.

This approach assumes the array doesn't contain duplicate values. If duplicates are allowed, additional checks might be needed during the comparison with the middle element.

• The rotated array is still partially sorted, that's why we can use binary search to find the target.
• If nums[left] <= nums[mid], the left half is sorted. If not, the right half is sorted.
• If the target is within the sorted half, binary search proceeds as usual. Otherwise, search the unsorted half.

Binary Search

Based on above key insights, at least one half of the array is sorted at each step. Use this to decide which half to search. This allows us to discard half of the array at each step -> maintain O(log N) time complexity.

Steps:

1. Split the array into two parts.
2. Identify which part is sorted. (the first value <= the last value, it's sorted when first <= last)
3. Check if the target is in the sorted part.
4. If yes, search that part, otherwise, search another part.

For example, nums = [6, 7, 0, 1, 2, 5], target = 3:

• The middle = 0, left part = [6, 7, 0], right part = [0, 1, 2, 5].
• We check which part is sorted by checking if the first element <= the last element in each part. The right part is sorted.
• Then we check if target in the range of sorted part, 3 in 0..5, so we search the right part.
• Otherwise, we search another part.
• So on...

fun search(nums: IntArray, target: Int): Int {
    var left = 0
    var right = nums.size - 1
    while (left <= right) {
        val middle = left + (right - left) / 2
        if (target == nums[middle]) return middle

        if (nums[left] <= nums[middle]) { // left part is sorted?
            if (target in nums[left]..nums[middle]) // Check if target in this sorted part
                right = middle - 1
            else 
                left = middle + 1
        } else {
            // Otherwise, right part is sorted.
            if (target in nums[middle]..nums[right]) // Check if target in this sorted part
                left = middle + 1
            else
                right = middle - 1
        }
    }
    return -1
}

• Time Complexity: O(log N), where N is the length of nums.
• Space Complexity: O(1).

Edge Cases

Consider the small test cases with odd and even size could be helpful:

• Array of size 1: [1], target is present or not.
• Array of size 2: [1,3] and [3,1], target is present or not.
• Target is at the pivot point (the smallest or largest element).
• Array is not rotated (fully sorted).
• Target is not present at all.

How to avoid:

• Always check nums[left] <= nums[mid] to determine the sorted half, not just <.
• Be careful with the range checks: use in nums[left]..nums[mid] and in nums[mid]..nums[right].

Pitfalls

• Using < instead of <= when checking if a half is sorted can cause infinite loops or miss the target.
• Not updating left and right correctly when the target is not in the sorted half.
• Forgetting to check for the target at mid before other logic.
• Off-by-one errors in the binary search loop, such as using left < right instead of left <= right or updating right = mid instead of right = mid - 1, which can cause infinite loops or miss elements at the boundaries.

Similar or Follow-up Problems

• 81. Search in Rotated Sorted Array II

TODO: Try to understand this approach: https://leetcode.com/problems/search-in-rotated-sorted-array/solutions/154836/the-inf-and-inf-method-but-with-a-better-explanation-for-dummies-like-me/

Suppose we have the rotated array: `[5, 6, 7, 0, 1, 2, 3]`
* If the target is `6` in left half, then we can search the left part, the array looks like `[5, 6, 7, oo, oo, oo, oo]`, it's still sorted. 
* If the target is `2` in right half, then we can search the right part, the array looks like `[-oo, -oo, -oo, 0, 1, 2, 3]`.

WA

• It leads to WA ([3,1], 1):

if (nums[left] < nums[middle]) {
    if (target in nums[left]..nums[middle])
        right = middle - 1
    else 
        left = middle + 1
} else {
    if (target in nums[middle]..nums[right])
        left = middle + 1
    else
        // Meet the condition and then break the while loop
        right = middle - 1
}

• It leads to TLE ([3,1], 0) because all the conditions don't meet:

// Not meet
if (nums[left] < nums[middle]) {
    if (target in nums[left]..nums[middle])
        right = middle - 1
    else 
        left = middle + 1
} else if (nums[middle] <= nums[right]) { // Not meet as well
    if (target in nums[middle]..nums[right])
        left = middle + 1
    else
        right = middle - 1
}