Search in Rotated Sorted Array

[MyrinNew]

In this task, I worked on finding a target element in a rotated sorted array using an efficient approach.


A rotated sorted array is one that was originally sorted but then rotated at some pivot point.

For example: [4, 5, 6, 7, 0, 1, 2]


What I Did

I created a function search that:

• Takes an array nums and a target value
• Returns the index of the target if found
• Returns -1 if the target does not exist

How I Solved It

Instead of using a linear search , I used a modified binary search.


Approach

I used two pointers:

• low starting from index 0
• high starting from index n - 1

Then I repeatedly calculated the middle index mid.


Logic Behind It

At each step:


1. Check if Middle is Target

• If nums[mid] == target, return mid

2. Identify the Sorted Half

Case 1: Left Half is Sorted

• If nums[low]
• Check if target lies between low and mid:
  • YES → move high = mid - 1
  • NO → move low = mid + 1

Case 2: Right Half is Sorted

• Otherwise, the right half is sorted
• Check if target lies between mid and high:
  • YES → move low = mid + 1
  • NO → move high = mid - 1

Code





class Solution:
def search(self, nums, target):
low, high = 0, len(nums) - 1

while low high:
mid = (low + high) // 2

if nums[mid] == target:
return mid

if nums[low] nums[mid]:
if nums[low] target nums[mid]:
high = mid - 1
else:
low = mid + 1
else:
if nums[mid] target nums[high]:
low = mid + 1
else:
high = mid - 1

return -1







How It Works

• Detects which side is properly sorted
• Narrows down the search space accordingly
• Repeats until it finds the target or exhausts the range

Time Complexity

• O(log n)

Example





nums = [4,5,6,7,0,1,2]
target = 0
Output: 4









More...