Lesson 3 � Intermediate
Search in Rotated Sorted Array
Rotated sorted array ek sorted array hai jo ek point pe rotate ho gaya hai. Jaise [4,5,6,7,0,1,2] � ye [0,1,2,4,5,6,7] ka rotated version hai. Binary search ke saath ismein bhi O(log n) mein search kar sakte ho!
Rotated Array concept
WHAT
Rotated sorted array mein sorted array ke kuch elements end se start pe move ho jaate hain. [0,1,2,4,5,6,7] ko 4 positions rotate karo toh [4,5,6,7,0,1,2] ban jaata hai. Array abhi bhi "partially sorted" hai.
WHEN
Jab interview mein rotated array ka question aaye � search, find minimum, find pivot. Ye LeetCode pe bahut common hai. Interviews mein ye test karta hai tumhara binary search adapt karne ki ability.
WHERE
Real world mein jab cyclic data ho (days of week, circular buffers), ya jab system restart hone pe state restore ho. Competitive coding mein ye standard pattern hai.
Visual: Rotation samjho
Original: [0, 1, 2, 4, 5, 6, 7]
Rotated: [4, 5, 6, 7, 0, 1, 2]
?
Pivot (minimum element)
Key observation:
- Pivot ke left mein: sab bada hai pivot se
- Pivot ke right mein: sab chhota hai pivot se
- Dono halves individually sorted hain!
Search karte waqt:
- Mid kis half mein hai wo check karo
- Target kis half mein ho sakta hai wo decide karoSearch in Rotated Array
def search_rotated(nums, target):
left, right = 0, len(nums) - 1
while left <= right:
mid = (left + right) // 2
if nums[mid] == target:
return mid
# Left half sorted hai
if nums[left] <= nums[mid]:
# Target left half mein ho sakta hai?
if nums[left] <= target < nums[mid]:
right = mid - 1
else:
left = mid + 1
# Right half sorted hai
else:
# Target right half mein ho sakta hai?
if nums[mid] < target <= nums[right]:
left = mid + 1
else:
right = mid - 1
return -1
# Usage
arr = [4, 5, 6, 7, 0, 1, 2]
print(search_rotated(arr, 0)) # 4
print(search_rotated(arr, 3)) # -1nums[left] <= nums[mid] hai toh left half sorted hai. Ab check karo target uss sorted half mein hai ya nahi. Bas!
Pivot / Minimum Element Find karo
Pivot wo element hai jo minimum hai � rotated array ka "break point":
def find_minimum(nums):
left, right = 0, len(nums) - 1
while left < right:
mid = (left + right) // 2
if nums[mid] > nums[right]:
# Minimum right mein hai
left = mid + 1
else:
# Minimum mid ya uske left mein hai
right = mid
return nums[left]
# Usage
arr = [4, 5, 6, 7, 0, 1, 2]
print(find_minimum(arr)) # 0
arr2 = [2, 3, 4, 5, 1]
print(find_minimum(arr2)) # 1# Pivot index find karna
def find_pivot(nums):
left, right = 0, len(nums) - 1
while left < right:
mid = (left + right) // 2
if nums[mid] > nums[right]:
left = mid + 1
else:
right = mid
return left
# Example
arr = [4, 5, 6, 7, 0, 1, 2]
print(find_pivot(arr)) # 4 (index of minimum element 0)Duplicates ke saath
Agar duplicates hain toh ek extra check lagana padta hai:
def search_with_duplicates(nums, target):
left, right = 0, len(nums) - 1
while left <= right:
mid = (left + right) // 2
if nums[mid] == target:
return mid
# Duplicate handling: left, mid, right equal ho sakte hain
if nums[left] == nums[mid] == nums[right]:
left += 1
right -= 1
continue
if nums[left] <= nums[mid]:
if nums[left] <= target < nums[mid]:
right = mid - 1
else:
left = mid + 1
else:
if nums[mid] < target <= nums[right]:
left = mid + 1
else:
right = mid - 1
return -1[1,1,1,1,1]). But average case mein O(log n) hi rehta hai.
Try it: code khud likho
Exercise
Question: Rotated sorted array [3, 4, 5, 1, 2] mein minimum element ka index kya hai✓ Answer mein index number daalo.
Question: Array [8, 9, 10, 1, 2, 3, 4, 5, 6, 7] mein element 3 ka index kya hai✓ Answer mein index number daalo.
Common mistakes
- Sab halves sorted hain assume karna: Rotated array mein sirf ek half sorted hota hai � left ya right. Dono nahi. Pehle check karo kaunsa sorted hai.
- Comparison galat karna:
nums[left] <= nums[mid]vsnums[left] < nums[mid]. Equal case handle karna zaroori hai jab single element ho. - Boundary conditions:
left <= rightvsleft < right. Search mein<=use karo (element mil sakta hai mid pe). Minimum find mein<use karo (converge karna hai). - Duplicates ignore karna: Agar duplicates hain toh
nums[left] == nums[mid] == nums[right]ka special case handle karo. Varna infinite loop ho sakta hai.
Rotated array samajh aa gaya✓ Ab Binary Search on Answer dekhte hain � ye sabse powerful pattern hai interview questions ke liye!