Search in Rotated Sorted Array

const search = (nums, target) => {
    let low = 0;
    let high = nums.length - 1;
 
    while (low <= high) {
        let mid = Math.floor((low + high) / 2);
        
        if (nums[mid] === target) {
            return mid;
        }
 
        // Check if the left half is sorted
        if (nums[low] <= nums[mid]) {
            // Check if target lies in the left half
            if (nums[low] <= target && target < nums[mid]) {
                high = mid - 1; // Search in the left half
            } else {
                low = mid + 1; // Search in the right half
            }
        } else { // Right half is sorted
            // Check if target lies in the right half
            if (nums[mid] < target && target <= nums[high]) {
                low = mid + 1; // Search in the right half
            } else {
                high = mid - 1; // Search in the left half
            }
        }
    }
    
    return -1; // Target not found
};
 
// Example usage:
const nums = [4, 5, 6, 7, 0, 1, 2];
const target = 0;
console.log(search(nums, target)); // Output: 4