Search in Rotated Sorted Array

You have given a rotated array sorted in ascending order. The array is rotated at some unknown `pivot` point. The array `[0,1,2,4,5,6,7]` might become `[4,5,6,7,0,1,2]`. You are given a target value to search. If found in the array return its index, otherwise return `-1`. You may assume no duplicate exists in the array. Your algorithm’s runtime complexity must be in the order of `O(log n)`.

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

The problem is to implement a search in `O(log(N))` time that gives an idea to use a binary search.

To understand how to find element in sorted rotated array, we must understand first, what is a sorted rotated array? An array is called sorted where for all `i` and `j` such that `i < j, A[i] <= A[j]`. A rotation happens when last element of array is push at the start and all elements on array move right by one position. This is called as rotation by 1. If new last element is also pushed to start again all elements are moved to right again, it’s rotation by 2 and so on.

Following is the Algorithm :

• Find a rotation index `rotationIndex`i.e. Actually this is the index of the smallest element in the array. Binary search works just perfect here.
• `rotationIndex` splits the array into two parts. Compare `nums[0]` and `target` to identify in which part one has to look for `target`.
• Perform a binary search in the chosen part of the array.
```class Solution {
int[] nums;
int target;

public int search(int[] nums, int target) {
if (nums == null || nums.length == 0) return -1;
if (nums.length == 1) {
return nums[0] == target ? 0 : -1;
}
this.nums = nums;
this.target = target;
int len = nums.length - 1;
int rotation = getRotationPoint();
// When there are no rotation
if (rotation == 0) return search(0, len);
// Search in the left part of the array
// First element can be the target
if (target >= nums[0]) return search(0, rotation);
// Search in the right part of the array
else return search(rotation, len);
}

private int getRotationPoint() {
int len = nums.length - 1;
// when there is no rotation
if (nums[0] < nums[len]) {
return 0;
}
int left = 0, right = len;
while (left < right) {
int mid = left + (right - left) / 2;
// Next element is the rotation point
if (nums[mid] > nums[mid + 1]) return (mid + 1);
else if (nums[mid] > nums[left]) left = (mid + 1);
else right = mid;
}
return 0;
}

// Binary Search for the target in the array
private int search(int left, int right) {
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) return mid;
if (nums[mid] > target) right = (mid - 1);
else left = (mid + 1);
}
return -1;
}
}
```

Complexity Analysis

• Time complexity : `O(log(N))`.
• Space complexity: `O(1)`

‘ ​

Categories: Binary Search