Introduction
This problem deals with searching an element in a sorted array which is rotated once. The pivot is unknown to us.
Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4
Input: nums = [4,5,6,7,0,1,2], target = 3
Output: -1Approach
One approach that might come up is to run the binary search to find the pivot and then search the element.
The interesting property of a sorted and rotated array is that when you divide it into two halves, atleast one of the two halves will always be sorted.
We can use this property and code it to search in the sorted half or non-sorted half. Refer to the program below that uses O(log n) time complexity and O(1) memory.
using System;
public class GFG {
static public void Main () {
var t = int.Parse(Console.ReadLine());
while (t > 0) {
var n = int.Parse(Console.ReadLine());
var a = new int[n];
var aStr = Console.ReadLine().Split(" ");
for (var i = 0; i < n; i++) {
a[i] = int.Parse(aStr[i]);
}
var k = int.Parse(Console.ReadLine());
Console.WriteLine(SearchRotated(a, 0, n - 1, k));
t--;
}
}
private static int SearchRotated(int[] a, int s, int e, int k) {
if (s > e) {
return -1;
}
var m = (e - s) / 2 + s;
if (a[m] == k) {
return m;
}
// first half is sorted
if (a[s] <= a[m]) {
if (a[s] <= k && a[m] >= k) {
return SearchRotated(a, s, m - 1, k);
} else {
return SearchRotated(a, m + 1, e, k);
}
}
// second half is sorted
if (a[m] <= k && a[e] >= k) {
return SearchRotated(a, m + 1, e, k);
} else {
return SearchRotated(a, s, m - 1, k);
}
}
}