Search in Bitonic Array
Given a bitonic array of numbers and a target value, find the index of the target value in the bitonic array in O(log n) time.
A bitonic array is an array that is first increasing and then decreasing.
Example 1:
Input : arr[] = {2, 4, 8, 10, 7, 6, 1}, target = 6
Output : 5Example 2:
Input: a[] = {2, 4, 6, 8, 10, 5, 3, 1}, target = 30
Output: -1 (target not found)Binary Search to find an element in a Bitonic Array
This problem is a variation of some of the existing problems we have already solved in this series:
Given that the array is first sorted in increasing order and then in decreasing order. If we can find the point at which it starts decreasing, then we can divide the array into two parts - the left part will be a sorted array in increasing order and the right part will be a sorted array in decreasing order. After that, we can apply binary search in both the array to find the element.
- Find the point at which the array starts decreasing. This point is the index of the maximum element (
maxIndex). - Apply binary search from
0 to maxIndexand frommaxIndex+1 to array_length-1.
import java.util.Scanner;
class SearchInBitonicArray {
// Bitonic Search
private static int search(int[] a, int target) {
int maxIndex = findMaxElement(a);
int targetIndex = binarySearch(a, 0, maxIndex, target);
if (targetIndex != -1) {
return targetIndex;
}
return binarySearch(a, maxIndex + 1, a.length - 1, target);
}
// Order agnostic binary search
private static int binarySearch(int[] a, int start, int end, int target) {
if (start > end) {
return -1;
}
int mid = (start + end) / 2;
if (target == a[mid]) {
return mid;
} else if ((a[start] < a[end] && target < a[mid]) || (a[start] > a[end] && target > a[mid])) {
return binarySearch(a, start, mid - 1, target);
} else {
return binarySearch(a, mid + 1, end, target);
}
}
// Find Max element in a Bitonic array
private static int findMaxElement(int[] a) {
int n = a.length;
int start = 0;
int end = n - 1;
while (start <= end) {
int mid = (start + end) / 2;
if ((mid == 0 || a[mid] > a[mid - 1]) && (mid == n - 1 || a[mid] > a[mid + 1])) {
return mid; // a[mid] is greater than both its neighbours. It is the maximum, return its index
} else if (a[mid] < a[mid - 1]) {
end = mid - 1; // a[mid] is smaller than its previous element, maximum lies in left half
} else {
start = mid + 1; // maximum lies in the right half
}
}
return -1;
}
public static void main(String[] args) {
Scanner keyboard = new Scanner(System.in);
int n = keyboard.nextInt();
int[] a = new int[n];
for(int i = 0; i < n; i++) {
a[i] = keyboard.nextInt();
}
int target = keyboard.nextInt();
keyboard.close();
System.out.printf("BinarySearchBitonicArray(%d) = %d%n", target, search(a, target));
}
}# Output
$ javac SearchInBitonicArray.java
$ java SearchInBitonicArray
7
2 4 8 10 7 6 1
6
BinarySearchBitonicArray(6) = 5
$ java SearchInBitonicArray
7
2 4 8 10 7 6 1
4
BinarySearchBitonicArray(4) = 1
$ java SearchInBitonicArray
7
2 4 8 10 7 6 1
9
BinarySearchBitonicArray(9) = -1