impl Solution {
    fn search(nums: Vec<i32>, target: i32) -> i32 {
        // Define the start and end indices of the search space.
        let mut left = 0;
        let mut right = nums.len() as i32 - 1;

        while left <= right {
            // Compute the middle index of the current search space.
            let mid = left + (right - left) / 2;

            // Check if the target is at the mid index.
            if nums[mid as usize] == target {
                return mid;
            }

            // Determine which part of the array is sorted.
            // Check if the left half is sorted.
            if nums[left as usize] <= nums[mid as usize] {
                // If the target is in the sorted left half, narrow the search to the left half.
                if target >= nums[left as usize] && target < nums[mid as usize] {
                    right = mid - 1;
                } else {
                    // Otherwise, search in the right half.
                    left = mid + 1;
                }
            } else {
                // The right half is sorted.
                // If the target is in the sorted right half, narrow the search to the right half.
                if target > nums[mid as usize] && target <= nums[right as usize] {
                    left = mid + 1;
                } else {
                    // Otherwise, search in the left half.
                    right = mid - 1;
                }
            }
        }

        // Return -1 if the target is not found.
        -1
    }
}