Searching in a Rotated Sorted Array Using Modified Binary Search in Python

Problem Explanation

You are given a sorted array nums that has been rotated at some unknown index.
Your task is to find the index of a target element.

If the target is not present, return -1.

Example:

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

• Input: nums = [4,5,6,7,0,1,2], target = 3
  Output: -1

• Input: nums = [1], target = 0
  Output: -1

---

Method Used: Modified Binary Search

Idea

Even though the array is rotated, one half is always sorted.

So:

• Check which half is sorted
• Decide where the target lies
• Continue binary search

---

Why This Method?

• Time complexity: O(log n)
• Efficient even after rotation
• No need to actually rotate back

---

Python Code with Explanation

class Solution:
    def search(self, nums, target):

Defines the function.

---

        left = 0
        right = len(nums) - 1

Initialize search range.

---

        while left <= right:

Run binary search loop.

---

            mid = (left + right) // 2

Find middle index.

---

            if nums[mid] == target:
                return mid

If target found, return index.

---

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

Check if left half is sorted.

---

                if nums[left] <= target < nums[mid]:
                    right = mid - 1

If target lies in left half, search left.

---

                else:
                    left = mid + 1

Otherwise search right half.

---

            else:

Right half must be sorted.

---

                if nums[mid] < target <= nums[right]:
                    left = mid + 1

If target lies in right half, search right.

---

                else:
                    right = mid - 1

Otherwise search left.

---

        return -1

If not found, return -1.

---

Complete Code

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

        while left <= right:
            mid = (left + right) // 2

            if nums[mid] == target:
                return mid

            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

---

Step-by-Step Example

Input:

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

Steps:

• Find sorted half
• Narrow search space
• Locate target

Output:

4

---

Key Takeaway

Even in rotated arrays, binary search can still be applied by identifying the sorted half in each step.

---