top of page

### Looking to master object-oriented and system design for tech interviews or career growth?

• Improve your system design and machine coding skills.

• Study with our helpful resources.

**We're in beta mode and would love to hear your feedback.

Search

# Rotated Sorted Array Search InterviewBit Solution

Problem: Rotated Sorted Array Search

Problem Description:

Given an array of integers A of size N and an integer B.

array A is rotated at some pivot unknown to you beforehand.

(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2 ).

You are given a target value B to search. If found in the array, return its index, otherwise, return -1.

You may assume no duplicate exists in the array.

Note:-

1. Array A was sorted in non-decreasing order before rotation.

2. Think about the case when there are duplicates. Does your current solution work? How does the time complexity change?

Input Format

`The first argument given is the integer array A. The second argument given is the integer B. `

Output Format

`Return index of B in array A, otherwise return -1 `

Constraints

```1 <= N <= 1000000
1 <= A[i] <= 10^9
all elements in A are disitinct. ```

For Example

```Input 1:
A = [4, 5, 6, 7, 0, 1, 2, 3]
B = 4
Output 1:
0
Explanation 1:
Target 4 is found at index 0 in A.```
```Input 2:
A = [5, 17, 100, 3]
B = 6
Output 2:
-1```

## Approach

Since before rotation, the array was sorted, this means that we can use binary search.

In a binary search algorithm, we have three indexes, low, mid and high.

The mid variable divides the array into two part, one is [low,mid] and another is [mid,high].

You can clearly see that, whatever the mid value we choose, there will be at least one part that will be sorted.

For example,

```A = [4, 5, 0, 1, 2, 3]

For low = 0, high = 5
mid = 0,
[A[low], A[mid]] = [4] // Sorted

mid = 1,
[A[low], A[mid]] = [4, 5] // Sorted

mid = 2,
[A[low], A[mid]] = [4, 5, 0] // Unsorted but,
[A[mid], A[high]] = [0, 1, 2, 3] // Sorted

Similarly you can check for other indexes.```

Once you know which part is sorted then it becomes quite easy to find which side you have to shift. See below code to understand conditions a bit further.

## Time & Space Complexity

`Time Complexity: O(logN)`
`Space Complexity: O(1)  `

- Ignoring space taken by input array, we have used only constant space.

Code in C++

Tags:

bottom of page