# 1. Introduction

The "Search in Rotated Sorted Array" problem is a variation of binary search. It involves a unique challenge where a sorted array has been rotated at some unknown pivot. The task is to efficiently find a target value in this rotated array. This problem is a good test of understanding how to modify binary search to handle non-standard scenarios.

## Problem

An integer array nums, sorted in ascending order and containing distinct values, is rotated at an unknown pivot index k. After rotation, the array becomes [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]. Given nums after the rotation and an integer target, the goal is to return the index of target in nums, or -1 if it is not present. The algorithm should have a runtime complexity of O(log n).

# 2. Solution Steps

1. Implement a modified binary search to account for the rotated array.

2. Identify the sorted portion of the array in each iteration.

3. Determine if the target lies within the sorted portion or the unsorted portion.

4. Adjust the search range based on where the target is likely to be.

5. Continue the search until the target is found or the search space is exhausted.

# 3. Code Program

``````def search(nums, target):
start, end = 0, len(nums) - 1

while start <= end:
mid = (start + end) // 2

# Check if the middle element is the target
if nums[mid] == target:
return mid

# Check if the left half is sorted
if nums[start] <= nums[mid]:
# If target is in the left half
if nums[start] <= target <= nums[mid]:
end = mid - 1
else:
start = mid + 1
# Right half is sorted
else:
# If target is in the right half
if nums[mid] <= target <= nums[end]:
start = mid + 1
else:
end = mid - 1

return -1

# Testing the function with examples
print(search([4,5,6,7,0,1,2], 0))
print(search([4,5,6,7,0,1,2], 3))

``````

```4
-1
```

### Explanation:

1. Modified Binary Search: The algorithm uses a binary search but with modifications to handle the rotation.

2. Identifying Sorted Half: In each iteration, it determines whether the left or right half of the array is sorted.

3. Target Search: The search range is adjusted based on whether the target is likely in the sorted or unsorted half.

4. Search Adjustment: Depending on the target's position relative to the middle element, the search space is narrowed down.

5. Result: The function returns the index of the target if found, or -1 if the target is not in the array.