33. Search in Rotated Sorted Array

Practice Dates

2024/05/11

Description

Link: https://leetcode.com/problems/search-in-rotated-sorted-array/description/

Solution

This solution use a modified binary search approach.

However, the condition is not elegant enough. In fact, we can first check whether the left array is sorted. If the left is a sorted array and the target is within the left and the middle, then we check the the left sorted array. Otherwise, check the right half array.

If the left array is not a sorted array, then the right array must be. If the target is within the middle and the right, then we check the right half sorted array. Otherwise, check the left half array.

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left_idx = 0, right_idx = nums.size() - 1;
        while (left_idx <= right_idx) {
            int middle_idx = left_idx + (right_idx - left_idx) / 2;
            int middle = nums[middle_idx];
            if (middle == target) {
                return middle_idx;
            } 

            int left = nums[left_idx], right = nums[right_idx];
            if (target > middle) {
                if( right >= target || (middle_idx < right_idx && nums[middle_idx+1] > right)) {
                    left_idx = middle_idx + 1;
                } else {
                    right_idx = middle_idx - 1;
                }
            } else {
                if ( left <= target || (middle_idx > left_idx && nums[middle_idx-1] < left) ) {
                    right_idx = middle_idx - 1;
                } else {
                    left_idx = middle_idx + 1;
                }
            }
        }

        return -1;
    }
};

Performance

Time complexity: O(logn)

The more elegant implementation

When the middle is not equal to the target, we then check whether the left is less than or equal to the middle element. If it is, then we can confirm that the left half array is an sorted array. We then check if the target is within the range from left to middle

The determination in the right array is the same.

Note that the following code is implemented in Rust.

impl Solution {
    pub fn search(nums: Vec<i32>, target: i32) -> i32 {
        let (mut left_idx, mut right_idx) = (0, nums.len() - 1);
        while (left_idx <= right_idx) {
            let middle_idx = left_idx + (right_idx - left_idx) / 2;
            let middle = nums[middle_idx];
            if middle == target {
                return middle_idx as i32;
            }

            let (left, right) = (nums[left_idx], nums[right_idx]);
            // The left half array is sorted.
            if left <= middle {
                if left <= target && target <= middle {
                    right_idx = middle_idx - 1;
                } else {
                    left_idx = middle_idx + 1;
                }
            } else {
                if (middle <= target && target <= right) {
                    left_idx = middle_idx + 1;
                } else {
                    right_idx = middle_idx - 1;
                }
            }

        }

        return -1;
    }
}

jason89521 / leetcode_note