February 27, 2021

Hello LeetCode enthusiasts π! Today we will be discussing a new array problem.

There is an integer array `nums`

sorted in ascending order (with distinct values).

Prior to being passed to your function, `nums`

is rotated at an unknown pivot index `k`

(`0 <= 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 rotation and an integer `target`

, return the index of target if it is in `nums`

, or -1 if it is not in `nums`

.

- 1 β€
`nums.length`

β€ 5000 - -10
^{4}β€`nums[i]`

β€ 10^{4} - All values of
`nums`

are unique. `nums`

is guaranteed to be rotated at some pivot.- -10
^{4}β€`target`

β€ 10^{4}.

Can you achieve this in `O(log n)`

time 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
```

This question is an extension of the binary search. The only catch here is that the array is rotated from an unknown index `k`

. For e.g., letβs say we have a sorted array `A = [1, 2, 3, 4, 5, 6]`

, and if I rotated it from index 3 then it will become `A = [4, 5, 6, 1, 2, 3]`

.

This still gives an illusion of an *unsorted* array, but it isnβt actually if we can find the index from where it is sorted.

The approach is simple if we are able to find the index from where the given array is rotated. We can follow below steps to solve this problem β

- Find the index where the array is rotated. Notice if a
*sorted*array is*rotated*then the rightmost element will not be the biggest element in the array. - Using the information in step #1, we can perform binary search to find the index where the array is rotated.
- Once we have found that index, then we can easily determine in which half (array will be divided into two halves by the pivot index) of the array the
`target`

lies. - Notice, the two halves are themselves will be sorted (this is pretty intuitive, right π?).
- We can then perform binary search once again in the determined half to find the index of the target element.

Since we are discarding one half of the array after every iteration, the time complexity will be ** O(log n)**.

We are not using any data structure for intermediate calculations, hence the space complexity would be ** O(1)**.

```
public class SearchInRotatedSortedArray {
public int search(int[] nums, int target) {
// Special case
if (nums == null || nums.length == 0) {
return -1;
}
// Left and right pointers in the array
int left = 0;
int right = nums.length - 1;
// First step is to find the pivot where the
// array is rotated
while (left < right) {
// Middle pointer
int middle = left + (right - left) / 2;
// If the element at the mid is greater than
// the element at the right then we can say that
// the array is rotated after middle index
if (nums[middle] > nums[right]) {
left = middle + 1;
}
// Else, the pivot is in the left part
else {
right = middle;
}
}
// After the above loop is completed, then the
// left index will point to the pivot
int pivot = left;
left = 0;
right = nums.length - 1;
// Now we will find in which half of the array,
// our target is present
if (target >= nums[pivot] && target <= nums[right]) {
left = pivot;
} else {
right = pivot;
}
// Now perform normal binary search
while (left <= right) {
int middle = left + (right - left) / 2;
if (nums[middle] == target) {
return middle;
} else if (target < nums[middle]) {
right = middle - 1;
} else {
left = middle + 1;
}
}
return -1;
}
}
```

```
def search(nums: List[int], target: int) -> int:
# Special case
if nums is None or len(nums) == 0:
return -1
# Left and right pointers for the array
left, right = 0, len(nums) - 1
# First step is to find the pivot where the array
# is rotated
while left < right:
# Middle index
middle = left + (right - left) // 2
# If the element at the mid is greater than
# the element at the right then we can say that
# the array is rotated after middle index
if nums[middle] > nums[right]:
left = middle + 1
# Else, the pivot is in the left part
else:
right = middle
# After the above loop is completed, then the
# left index will point to the pivot
pivot = left
left, right = 0, len(nums) - 1
# Now we will find in which half of the array,
# our targetValue is present
if nums[pivot] <= target <= nums[right]:
left = pivot
else:
right = pivot
# Now perform normal binary search
while left <= right:
middle = left + (right - left) // 2
if nums[middle] == target:
return middle
elif nums[middle] < target:
left = middle + 1
else:
right = middle - 1
return -1
```

```
var search = function (nums, target) {
// Special case
if (nums === null || nums.length === 0) {
return -1;
}
// Left and right pointers in the array
let left = 0;
let right = nums.length - 1;
// First step is to find the pivot where the
// array is rotated
while (left < right) {
// Middle pointer
let middle = left + parseInt((right - left) / 2);
// If the element at the mid is greater than
// the element at the right then we can say that
// the array is rotated after middle index
if (nums[middle] > nums[right]) {
left = middle + 1;
}
// Else, the pivot is in the left part
else {
right = middle;
}
}
// After the above loop is completed, then the
// left index will point to the pivot
const pivot = left;
left = 0;
right = nums.length - 1;
// Now we will find in which half of the array,
// our target is present
if (target >= nums[pivot] && target <= nums[right]) {
left = pivot;
} else {
right = pivot;
}
// Now perform normal binary search
while (left <= right) {
let middle = left + parseInt((right - left) / 2);
if (nums[middle] === target) {
return middle;
} else if (target < nums[middle]) {
right = middle - 1;
} else {
left = middle + 1;
}
}
return -1;
};
```

```
fun search(nums: IntArray, target: Int): Int {
// Special case
if (nums.isEmpty()) {
return -1
}
// Left and right pointers in the array
var left = 0
var right = nums.size - 1
// First step is to find the pivot where the
// array is rotated
while (left < right) {
// Middle pointer
val middle = left + (right - left) / 2
// If the element at the mid is greater than
// the element at the right then we can say that
// the array is rotated after middle index
if (nums[middle] > nums[right]) {
left = middle + 1
} else {
right = middle
}
}
// After the above loop is completed, then the
// left index will point to the pivot
val pivot = left
left = 0
right = nums.size - 1
// Now we will find in which half of the array,
// our target is present
if (target >= nums[pivot] && target <= nums[right]) {
left = pivot
} else {
right = pivot
}
// Now perform normal binary search
while (left <= right) {
val middle = left + (right - left) / 2
if (nums[middle] == target) {
return middle
} else if (target < nums[middle]) {
right = middle - 1
} else {
left = middle + 1
}
}
return -1
}
```

Congratulations π! Today we solved another LeetCode problem which was an extension to the normal binary search.

I hope you enjoyed this post. Feel free to share your thoughts on this.

You can find the complete source code on my GitHub repository. If you like what you learn, feel free to fork πͺ and star β it.

Till next timeβ¦ Happy coding π and Namaste π!