Search In Rotated Sorted Array

You are given a sorted integer array, nums, and an integer value, target. This array has been rotated by some unknown number of positions.

Search in a Rotated Sorted Array

Problem Statement

You are given a sorted integer array, nums, and an integer value, target. This array has been rotated by some unknown number of positions.

Search for target in this array, and return its index. If target does not exist in the array, return -1.

Example of Rotation

Here is an original sorted array, before rotation:

1, 10, 20, 47, 59, 63, 75, 88, 99, 107, 120, 133, 155, 162, 176, 188, 199, 200, 210, 222

After rotating this array 6 times, it becomes:

176, 188, 199, 200, 210, 222, 1, 10, 20, 47, 59, 63, 75, 88, 99, 107, 120, 133, 155, 162

Constraints

• All values in nums are unique.
• The values in nums were sorted in ascending order before rotation.
• The array may have been rotated by any number of positions.
• 1 ≤ nums.length ≤ 1000
• −10⁴ ≤ nums[i] ≤ 10⁴
• −10⁴ ≤ target ≤ 10⁴

Solution

Since the array has been rotated, it's not as simple as a normal binary search. We can't always tell which half of the array to eliminate just by comparing values directly.

However, there's a useful pattern: whenever we're at the middle of the array, at least one half (either the left half or the right half) is guaranteed to still be sorted normally.

So the approach becomes:

• Find the middle element.
• Figure out which half is sorted: the left half or the right half.
• Check if the target falls within the range of that sorted half.
  • If it does, we can safely search inside that sorted half, and eliminate the other half.
  • If it doesn't, we move to the other half instead, since the target must be there (if it exists at all).
• We repeat this process. Each time, whichever half we move into will again have one sorted part and one rotated part, so the same logic keeps applying.

Two Main Cases

1. The left part (low to mid) is sorted.

   • If target falls between nums[low] and nums[mid], search the left half.
   • Otherwise, search the right half.

2. The right part (mid to end) is sorted.

   • If target falls between nums[mid] and nums[end], search the right half.
   • Otherwise, search the left half.

Code

function binarySearchRotated(nums, target) {
    let low = 0,
        end = nums.length - 1;

    while (low <= end) {
        let mid = low + Math.floor((end - low) / 2);
        if (nums[mid] == target) {
            return mid;
        }

        if (nums[low] <= nums[mid]) {
            if (nums[low] <= target && target < nums[mid]) {
                end = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        else {
            if (nums[mid] < target && target <= nums[end]) {
                low = mid + 1;
            } else {
                end = mid - 1;
            }
        }
    }
    return -1;
};