Search in a Rotated Sorted Array
Problem
A sorted array of different values was rotated at an unknown place (for example 0 1 2 4 5 6 7 became 4 5 6 7 0 1 2). Print the index of k, or -1 if k is not there. Use O(log n) time.
Constraints
- 1 <= n <= 10^5
- All values are different
Examples
Input
7 4 5 6 7 0 1 2 0
Output
4
Solutions
After the rotation, at least one half around the middle is still sorted. We check whether k falls inside the sorted half and discard the other half. The values must be different, or the sorted-half test can fail.
/*
* Problem : Search in an array.
* Input : n, then n integers, then k.
* Output : The index or -1.
* Approach: Find the sorted half.
* Time : O(log n)
* Space : O(1)
* Java : 8 or newer.
*/
import java.util.Scanner;
public class Main {
// This method solves the task. It receives the input and returns the answer.
static int solve(int[] a, int k) {
int low = 0;
int high = a.length - 1;
while (low <= high) {
int mid = low + (high - low) / 2;
if (a[mid] == k) {
return mid;
}
// Step 1: One half is always sorted. If the left half is sorted ...
if (a[low] <= a[mid]) {
// Step 2: ... and k is inside it, search the left half. Else search the right half.
if (a[low] <= k && k < a[mid]) {
high = mid - 1;
} else {
low = mid + 1;
}
} else {
// Step 3: Otherwise the right half is sorted. Do the same check there.
if (a[mid] < k && k <= a[high]) {
low = mid + 1;
} else {
high = mid - 1;
}
}
}
return -1;
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int size = scanner.nextInt();
int[] a = new int[size];
for (int i = 0; i < size; i++) {
a[i] = scanner.nextInt();
}
int k = scanner.nextInt();
System.out.println(solve(a, k));
}
}
Hints (1)
- Why is one half always sorted?