Binary search template

template.java

int x = -1;
int z = n / 2; // any sane large enough value to split problem space
for (int b = z; b >= 1; b /= 2) {
  while (f(x+b) < f(x+b+1)) x += b;
}
int k = x+1;


for (int b = z; b >= 1; b /= 2) {
   while (!ok(x+b)) x += b;
}