🌱 Keegan's Digital Garden

33. Search in Rotated Sorted Array

2 min read

Leetcode

📝 Problem Details

💭What Were My Initial Thoughts?

- brute force would be to just iterate through the array and check if the current value equals our target
	- this will not fit the time complexity requirement of O(log n) however
- if the array was sorted, a binary search would be a simple solution
- maybe we can still employ binary search since the array is partially sorted
- the array also has two primary components based on where the rotation finishes

🤔What Did I Struggle With?

figuring out how to action the use of binary search in this case

💡 Explanation of Solution

1. use binary search to find the target
2. identify the sorted half: for each iteration determine whether the left or right half of the array is sorted by comparing nums[left] and nums[mid]
3. search in the sorted half
4. continue 2 and 3 until the target index is found or return 01

⌛ Complexity Analysis

Time Complexity: O(log n) based on the requireemnts of the problem

Space Compelxity: O(1)

💻 Implementation of Solution

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left = 0;
        int right = nums.size() - 1;
 
        while (left <= right) {
            int mid = left + (right - left) / 2; // Compute the middle index
            
            if (nums[mid] == target) return mid; // If the middle element is the target, return its index
            
            // Check which half is **sorted**
            if (nums[left] <= nums[mid]) { // **Left half is sorted**
                // Check if the target is **within the sorted left half**
                if (nums[left] <= target && nums[mid] >= target) 
                    right = mid - 1; // Search in the left half
                else 
                    left = mid + 1;  // Search in the right half (unsorted part)
            } 
            else { // **Right half is sorted**
                // Check if the target is **within the sorted right half**
                if (nums[mid] <= target && nums[right] >= target) 
                    left = mid + 1; // Search in the right half
                else 
                    right = mid - 1; // Search in the left half (unsorted part)
            }
        }
        return -1; // Target was not found
    }
};

Graph View