## Table of contents

## Open Table of contents

## Problem

There is an integer array `nums`

sorted in ascending order (with **distinct** values).

Prior to being passed to your function, `nums`

is **possibly rotated** at an unknown pivot index `k`

(`1 <= k < nums.length`

) such that the resulting array is `[nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]`

(**0-indexed**). For example, `[0,1,2,4,5,6,7]`

might be rotated at pivot index `3`

and become `[4,5,6,7,0,1,2]`

.

Given the array `nums`

**after** the possible rotation and an integer `target`

, return *the index of* `target`

*if it is in* `nums`

*, or* `-1`

*if it is not in* `nums`

.

You must write an algorithm with `O(log n)`

runtime complexity.

**Example 1:**

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

**Example 2:**

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

**Example 3:**

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

**Constraints:**

`1 <= nums.length <= 5000`

`-10^4 <= nums[i] <= 10^4`

- All values of
`nums`

are**unique**. `nums`

is an ascending array that is possibly rotated.`-10^4 <= target <= 10^4`

## Explanation/Approach

Given a sorted and rotated array, the goal is to find the index of a target value efficiently (with O(log n) time complexity). To achieve logarithmic time complexity, we can use a modified version of binary search.

The primary challenge here is dealing with the rotation in the array. First, identify whether the target value resides in the rotated part or the sorted part of the array. Then proceed with binary search in the identified subarray.

**Step 1:**Find the middle element of the array.**Step 2:**Determine which part of the array is sorted (either the left or right half).**Step 3:**Check if the target resides within the sorted part. If so, discard the other half. If not, discard the sorted half.**Step 4:**Repeat the process until you find the target or the search space is empty.

## Solution (Modified Binary Search)

```
class Solution:
def search(self, nums: List[int], target: int) -> int:
# Define the start and end pointers
start = 0
end = len(nums) - 1
# Continue the search while start is less than or equal to end
while start <= end:
mid = start + (end - start) // 2 # Find the middle element
# If target is found, return its index
if nums[mid] == target:
return mid
# Determine if left half is sorted
if nums[start] <= nums[mid]:
# If target is in the sorted left half, update end pointer
if nums[start] <= target <= nums[mid]:
end = mid - 1
# Otherwise, update start pointer
else:
start = mid + 1
# If right half is sorted
else:
# If target is in the sorted right half, update start pointer
if nums[mid] <= target <= nums[end]:
start = mid + 1
# Otherwise, update end pointer
else:
end = mid - 1
# If target is not found, return -1
return -1
```

**Explanation**

- Set
`start`

and`end`

pointers at the beginning and end of`nums`

. - Enter a loop that continues as long as
`start`

is less than or equal to`end`

. - Calculate the
`mid`

index and check if`nums[mid]`

is the`target`

. If yes, return`mid`

. - Check which half of the array is sorted by comparing
`nums[start]`

and`nums[mid]`

. - Determine if the
`target`

is within the sorted half by comparing it with`nums[start]`

and`nums[mid]`

(or`nums[mid]`

and`nums[end]`

for the right half). - If
`target`

is in the sorted half, adjust`start`

or`end`

to search within it; otherwise, search in the other half. - Repeat the process until
`start`

exceeds`end`

or the target is found.

**Time and Memory Complexity**

**Time Complexity:**O(log n) due to the modified binary search algorithm that reduces the search space in half with each iteration.**Space Complexity:**O(1), since the algorithm uses a constant amount of space regardless of the input size.