ASSIGNMENT 20

1. Search in Rotated Sorted Array

Problem

You are given a sorted array that has been rotated at an unknown pivot, and a target value.
Your task is to return the index of the target if found, otherwise return -1. 

Example

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

Output:
4

Approach Used

Modified Binary Search

Since the array is rotated, it is not fully sorted.
But an important observation helps:

At least one half of the array is always sorted 

Using this property, we modify binary search to decide which half to explore.

Step-by-Step Explanation

Step 1: Initialize Search Space

Start with two pointers:
•Left at the beginning
•Right at the end

Step 2: Find Middle Element

Find the middle index of the current search space.

Step 3: Check Target
•If the middle element equals the target → return index
•Otherwise → continue searching

Step 4: Identify Sorted Half

Check which half is sorted:
•If left element ≤ middle element → left half is sorted
•Otherwise → right half is sorted 

Step 5: Decide Where Target Lies

Now check if the target lies in the sorted half:

Case 1: Left Half is Sorted
•If target lies between left and middle → search left
Otherwise → search right

Case 2: Right Half is Sorted
•If target lies between middle and right → search right
•Otherwise → search left

Step 6: Reduce Search Space

Discard the half where the target cannot exist.
This reduces the search space by half.

Step 7: Repeat

Continue the process until:
•Target is found OR Search space becomes empty

CODE:

`class Solution:
# @param {integer[]} numss
# @param {integer} target
# @return {integer}
def search(self, nums, target):
if not nums:
return -1

    low, high = 0, len(nums) - 1

    while low <= high:
        mid = (low + high) / 2
        if target == nums[mid]:
            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`

Conclusion

The key idea in this problem is recognizing that even after rotation, the array retains partial order. By identifying the sorted half and checking where the target lies, we can efficiently apply binary search.