How do you solve Search in Rotated Sorted Array on LeetCode?

Search in Rotated Sorted Array (LeetCode #33) can be solved using Brute Force or Optimal Solution (Binary Search). The optimal approach is Optimal Solution (Binary Search) with O(log n) time complexity and O(1) space complexity. Key insight: The key observation is that the array is divided into two sorted halves. This allows us to determine which half to search based on the target's value.

What is the brute force solution for Search in Rotated Sorted Array?

The brute force approach for Search in Rotated Sorted Array is Brute Force, with O(n) time complexity and O(1) space complexity. The brute force approach involves scanning through the entire array to find the target. Since the array is rotated, we cannot directly apply binary search, so we simply check each element one by one. The optimal Optimal Solution (Binary Search) approach improves this to O(log n).

What algorithm or data structure is used to solve Search in Rotated Sorted Array?

Search in Rotated Sorted Array uses the following concepts: Array, Binary Search. The recommended patterns to study are: Binary Search, Array, Two Pointers.

What are the interview tips for Search in Rotated Sorted Array?

When you first see this problem, mention that you recognize it's a binary search problem but with a twist due to the rotation. Communicate your approach clearly, explaining how you will identify the sorted half and decide where to search next. Be sure to mention edge cases, such as when the array has only one element or when the target is not present.

What are common mistakes when solving Search in Rotated Sorted Array?

Students often forget to check both halves of the array and may assume the entire array is sorted, leading to incorrect results. Another common mistake is not handling the case where the left and right pointers are equal, which can lead to infinite loops.

#33

Search in Rotated Sorted Array

Medium

ArrayBinary SearchBinary SearchArrayTwo Pointers

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution (Binary Search)★
Time	O(n)	O(log n)
Space	O(1)	O(1)

💡

Intuition

Time O(log n)Space O(1)

The optimal solution uses a modified binary search to efficiently locate the target in the rotated sorted array. By determining which half of the array is sorted, we can decide whether to search in the left or right half.

⚙️

Algorithm

7 steps

1Step 1: Initialize two pointers, left and right, to the start and end of the array.
2Step 2: While left is less than or equal to right, calculate the mid index.
3Step 3: Check if nums[mid] is the target; if so, return mid.
4Step 4: Determine if the left half is sorted by comparing nums[left] and nums[mid].
5Step 5: If the left half is sorted, check if the target is within this range. If yes, move right to mid - 1; otherwise, move left to mid + 1.
6Step 6: If the left half is not sorted, it means the right half must be sorted. Check if the target is within this range. If yes, move left to mid + 1; otherwise, move right to mid - 1.
7Step 7: If the target is not found, return -1.

solution.py19 lines

1# Full working Python code with comments
2
3def search(nums, target):
4    left, right = 0, len(nums) - 1
5    while left <= right:
6        mid = (left + right) // 2
7        if nums[mid] == target:
8            return mid
9        if nums[left] <= nums[mid]:  # Left half is sorted
10            if nums[left] <= target < nums[mid]:
11                right = mid - 1
12            else:
13                left = mid + 1
14        else:  # Right half is sorted
15            if nums[mid] < target <= nums[right]:
16                left = mid + 1
17            else:
18                right = mid - 1
19    return -1

ℹ

Complexity note: This complexity is achieved because we are effectively halving the search space with each iteration, similar to standard binary search.

1The key observation is that the array is divided into two sorted halves. This allows us to determine which half to search based on the target's value.
2Understanding the properties of binary search and how they apply to rotated arrays is crucial for solving similar problems efficiently.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.