PROBLEM DESCRIPTION
Given a bitonic sequence A of N distinct elements, write a program to find a given element B in the bitonic sequence in O(logN) time.
NOTE:
A Bitonic Sequence is a sequence of numbers which is first strictly increasing then after a point strictly decreasing.
Problem Constraints
- 3 <= N <= 105
- 1 <= A[i], B <= 108
- Given array always contain a bitonic point.
- Array A always contain distinct elements.
SOLUTION
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
public class Solution {
public int solve(int[] A, int B) {
// Find the pivot point where the sequence transitions from increasing to decreasing
int pivot = findPivot(A);
// Perform binary search twice:
// First time on the left part (increasing) and then on the second part
int idx = binarySearchInRange(A, B, 0, pivot, true); // Search in the increasing part
if(idx == -1)
idx = binarySearchInRange(A, B, pivot+1, A.length-1, false); // Search in the decreasing part
return idx;
}
// Binary search within a specified range of the sequence
public int binarySearchInRange(int[] A, int B, int l, int r, boolean isIncreasing){
while(l <= r){
int m = (l+r)/2; // midpoint
if(A[m] == B){ // If the element is found at the midpoint
return m; // Return its index
}
if(isIncreasing){ // If searching in the increasing part
// If the target is greater than the middle element
if(B > A[m]){
l = m+1; // Look towards the right
} else {
r = m-1; // Otherwise, look towards the left
}
} else { // If searching in the decreasing part
if(B < A[m]){ // If the target is less than the middle element
l = m+1; // Look towards the right
} else {
r = m-1; // Look towards the left
}
}
}
return -1; // If the element is not found, return -1
}
public int findPivot(int[] A){
int n = A.length;
int l = 0;
int r = n-1;
while(l <= r){
int m = (l+r)/2; // Calculate the midpoint
if(A[m] > A[m-1] && A[m] < A[m+1]){ // If the middle element is the pivot
return m; // Return its index
} else if(A[m] > A[m-1]){ // If the sequence is increasing
l = m+1; // Adjust the search range to the right half
} else { // If the sequence is decreasing
r = m-1; // Adjust the search range to the left half
}
}
return 0; // Default pivot index (shouldn't reach here in a valid bitonic sequence)
}
}