Binary Search - broyda/cp-lib GitHub Wiki
#Monotonic function
0 0 0 0 0 1 1 1 1
Bitonic function
For example, first increases (reaches to a maximum) and then decreases
11 15 16 4 3 1 (Max value is 16) ? /\
Standard template
#include <bits/stdc++.h>
using namespace std;
int n;
int arr[10005];
int check(int x) {
// return a[x] > a; // Upper bound (smallest number strictly greater than 'a')
// return a[x] >= a; // Lower bound (smallest number greater than or equal to 'a')
return 1;
}
void solve() {
cin >> n;
for (int i = 0; i < n; i++) {
cin >> arr[i];
}
int low = 0;
int high = n - 1;
int ans = 0; // ##
while (low <= high) {
int mid = (low + high) / 2;
if (check(mid)) {
ans = mid;
high = mid - 1; // First occurance of
} else {
low = mid + 1;
}
}
cout << ans << endl;
}