33. Search in Rotated Sorted Array

Problem

Search in Rotated Sorted Array - LeetCodeLeetCode

Intuition

Since the array is rotated, we cannot eliminate left or right half just like that. We need to check which half we need to eliminate.

• To check if the first half is sorted

nums[low] <= nums[mid] // It means left half is sorted

• In other cases, it means right half is sorted

Once we know which part of the array we need to search, we check if the given target is in range

• If the target is in left part, then search towards left, else right

• If target is in right part, then search towards right, else left

Time Complexity

O(log n)

Space Complexity

O(n)

Solution

class Solution {
    public int search(int[] nums, int target) {
        int low = 0, high = nums.length - 1;
        int result = -1;

        while(low <= high) {
            int mid = low + (high-low)/2;

            if(nums[mid] == target) { // Target found
                return mid;
            }

            if(nums[low] <= nums[mid]) { // Left sorted
                if(nums[low] <= target && target < nums[mid]) { // Search left
                    high = mid - 1;
                } else { // Search towards right
                    low = mid + 1;
                }
            } else { // Right sorted
                if(nums[mid] < target && target <= nums[high]) { // Search right
                    low = mid + 1;
                } else { // Search towards left
                    high = mid - 1;
                }
            }
        }
        return result;
    }
}