🔄 Search in Rotated Sorted Array – Python (Binary Search)

Hi All,

Today I solved an important problem: Search in Rotated Sorted Array using Binary Search.

📌 Problem Statement

Given a sorted array that is rotated at some pivot, find the index of a target element.

👉 If not found, return -1.

🔍 Examples

Example 1:

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

target = 0

Output:

4

Example 2:

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

target = 3

Output:

-1

Example 3:

nums = [1]

target = 0

Output:

-1

💡 Key Insight

👉 Even though the array is rotated:

• One half of the array is always sorted
  

💡 Approach

🔹 Modified Binary Search

1. Find mid
   


2. Check which half is sorted:
   
   
   
   
   • Left half sorted → check if target is inside
     
   
   
   • Right half sorted → check if target is inside
     
   
   
   
   

🧠 Step-by-Step Logic

• If nums[left] <= nums[mid] → Left part is sorted
  


• Else → Right part is sorted
  

Then:

• Decide where to search next
  

💻 Python Code

def search(nums, target):

    left = 0

    right = len(nums) - 1



    while left <= right:

        mid = (left + right) // 2



        if nums[mid] == target:

            return mid



        # Left half sorted

        if nums[left] <= nums[mid]:

            if nums[left] <= target < nums[mid]:

                right = mid - 1

            else:

                left = mid + 1



        # Right half sorted

        else:

            if nums[mid] < target <= nums[right]:

                left = mid + 1

            else:

                right = mid - 1



    return -1

🔍 Dry Run

For:

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

target = 0

Steps:

• mid = 3 → nums[mid] = 7
  


• Left sorted → target not in left → go right
  


• mid = 5 → nums[mid] = 1
  


• Right sorted → target in right → move left
  


• mid = 4 → nums[mid] = 0 → found
  

🖥️ Sample Output

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

Output: 4



Input: [4,5,6,7,0,1,2], target = 3

Output: -1

⚡ Complexity Analysis

• Time Complexity: O(log n) ✅
  


• Space Complexity: O(1) ✅
  

🧠 Why this is important?

• Combines binary search + logic thinking
  


• Common interview problem
  


• Tests understanding of rotated arrays
  

✅ Conclusion

This problem helped me understand:

• Modified binary search
  


• Handling rotated arrays
  


• Efficient searching techniques
  

🚀 Must-know problem for coding interviews!