.png)
Search in Rotated Sorted Array
Problem Statement
You are given a rotated sorted array of distinct integers and a target value.
Your task is to determine the index of the target element.
If the target is not present, return -1.
Example 1
Input
arr = [4, 5, 6, 7, 0, 1, 2]
target = 0
Output
4
Example 2
Input
arr = [4, 5, 6, 7, 0, 1, 2]
target = 3
Output
-1
Why This Problem Is Important
- Classic binary search variation
- Tests ability to reason about rotated sorted arrays
- Reduces search space logically
- Frequently asked in technical interviews
- Builds intuition for rotation-based problems
Key Observations
- One half of the array is always sorted
- Compare target with sorted half to decide search direction
- Achieves O(log n) time complexity
Approach 1: Linear Search
Idea
Traverse the array and check each element.
Algorithm
- Loop through the array
- If arr[i] == target, return i
- If not found, return -1
Time & Space Complexity
- Time: O(n)
- Space: O(1)
Approach 1: Linear Search
Idea
Traverse the array and check each element. If found, return index, else return -1.
Time Complexity: O(n)
Space Complexity: O(1)
C Implementation
#include
int main() {
int arr[] = {4, 5, 6, 7, 0, 1, 2};
int target = 0;
int n = sizeof(arr) / sizeof(arr[0]);
for(int i = 0; i < n; i++) {
if(arr[i] == target) {
printf("Index = %d\n", i);
return 0;
}
}
printf("Index = -1\n");
return 0;
}
Output
Index = 4
C++ Implementation
#include
using namespace std;
int main() {
int arr[] = {4, 5, 6, 7, 0, 1, 2};
int target = 0;
int n = sizeof(arr) / sizeof(arr[0]);
for(int i = 0; i < n; i++) {
if(arr[i] == target) {
cout << "Index = " << i << endl;
return 0;
}
}
cout << "Index = -1" << endl;
return 0;
}
Output
Index = 4
Java Implementation
public class LinearSearchRotatedArray {
public static void main(String[] args) {
int[] arr = {4, 5, 6, 7, 0, 1, 2};
int target = 0;
for(int i = 0; i < arr.length; i++) {
if(arr[i] == target) {
System.out.println("Index = " + i);
return;
}
}
System.out.println("Index = -1");
}
}
Output
Index = 4
Python Implementation
arr = [4, 5, 6, 7, 0, 1, 2]
target = 0
for i in range(len(arr)):
if arr[i] == target:
print("Index =", i)
break
else:
print("Index = -1")
Output
Index = 4
JavaScript Implementation
let arr = [4, 5, 6, 7, 0, 1, 2];
let target = 0;
let found = -1;
for (let i = 0; i < arr.length; i++) {
if (arr[i] === target) {
found = i;
break;
}
}
console.log("Index =", found);
Output
Index = 4
Next: Approach 2 – Modified Binary Search (Optimal O(log n)).
Approach 2: Modified Binary Search (Optimal)
Idea
At every step:
- One half is sorted
- Decide whether the target lies in the sorted half
Algorithm
Initialize:
low = 0 high = n - 1- While low <= high:
- Compute mid
- If arr[mid] == target, return mid
- If left half is sorted (arr[low] <= arr[mid]):
If target lies between arr[low] and arr[mid]
high = mid - 1Else
low = mid + 1
- Else (right half is sorted):
If target lies between arr[mid] and arr[high]
low = mid + 1Else
high = mid - 1
- If loop ends, return -1
Time & Space Complexity
- Time: O(log n)
- Space: O(1)
C Implementation
#include
int main() {
int arr[] = {4, 5, 6, 7, 0, 1, 2};
int target = 0;
int n = sizeof(arr) / sizeof(arr[0]);
int low = 0, high = n - 1;
while (low <= high) {
int mid = low + (high - low) / 2;
if (arr[mid] == target) {
printf("Index = %d\n", mid);
return 0;
}
// Left half sorted
if (arr[low] <= arr[mid]) {
if (target >= arr[low] && target < arr[mid])
high = mid - 1;
else
low = mid + 1;
}
// Right half sorted
else {
if (target > arr[mid] && target <= arr[high])
low = mid + 1;
else
high = mid - 1;
}
}
printf("Index = -1\n");
return 0;
}
Output
Index = 4
C++ Implementation
#include
using namespace std;
int main() {
int arr[] = {4, 5, 6, 7, 0, 1, 2};
int target = 0;
int n = sizeof(arr) / sizeof(arr[0]);
int low = 0, high = n - 1;
while (low <= high) {
int mid = low + (high - low) / 2;
if (arr[mid] == target) {
cout << "Index = " << mid << endl;
return 0;
}
if (arr[low] <= arr[mid]) {
if (target >= arr[low] && target < arr[mid])
high = mid - 1;
else
low = mid + 1;
} else {
if (target > arr[mid] && target <= arr[high])
low = mid + 1;
else
high = mid - 1;
}
}
cout << "Index = -1" << endl;
return 0;
}
Output
Index = 4
Java Implementation
public class SearchInRotatedSortedArray {
public static void main(String[] args) {
int[] arr = {4, 5, 6, 7, 0, 1, 2};
int target = 0;
int low = 0, high = arr.length - 1;
while (low <= high) {
int mid = low + (high - low) / 2;
if (arr[mid] == target) {
System.out.println("Index = " + mid);
return;
}
if (arr[low] <= arr[mid]) {
if (target >= arr[low] && target < arr[mid])
high = mid - 1;
else
low = mid + 1;
} else {
if (target > arr[mid] && target <= arr[high])
low = mid + 1;
else
high = mid - 1;
}
}
System.out.println("Index = -1");
}
}
Output
Index = 4
Python Implementation
arr = [4, 5, 6, 7, 0, 1, 2]
target = 0
low, high = 0, len(arr) - 1
while low <= high:
mid = (low + high) // 2
if arr[mid] == target:
print("Index =", mid)
break
if arr[low] <= arr[mid]:
if arr[low] <= target < arr[mid]:
high = mid - 1
else:
low = mid + 1
else:
if arr[mid] < target <= arr[high]:
low = mid + 1
else:
high = mid - 1
else:
print("Index = -1")
Output
Index = 4
JavaScript Implementation
let arr = [4, 5, 6, 7, 0, 1, 2];
let target = 0;
let low = 0, high = arr.length - 1;
while (low <= high) {
let mid = Math.floor((low + high) / 2);
if (arr[mid] === target) {
console.log("Index =", mid);
break;
}
if (arr[low] <= arr[mid]) {
if (target >= arr[low] && target < arr[mid])
high = mid - 1;
else
low = mid + 1;
} else {
if (target > arr[mid] && target <= arr[high])
low = mid + 1;
else
high = mid - 1;
}
if (low > high) console.log("Index = -1");
}
Output
Index = 4
Summary
- Rotated sorted array still allows binary search.
- One half is always sorted
- Efficient O(log n) solution
- Essential interview problem
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
