Hikari9's blog

Cleaner ternary search for arrays
By Hikari9, history, 8 years ago, In English

When I do ternary search for floating points, I normally do it like this:

while (R - L > EPS) {
  double M1 = (2*L + R) / 3;
  double M2 = (L + 2*R) / 3;
  if (f(M1) <= f(M2)) R = M2;
  else L = M1;
}
return f(L);

It works perfectly, but when I try to do it with bitonic arrays (with integer indices), I sometimes get the wrong value, either because I'm off by 1 or because some edge cases don't work.

while (L < R) {
  int M1 = (2*L + R) / 3;
  int M2 = (L + 2*R) / 3;
  if (a[M1] <= a[M2]) R = M2;
  else L = M1;
}
return a[L]; // doesn't work :(

I try to address this by looping at the end when the search space is small enough. This addresses the small edge cases and off by 1 errors.

while (L + 3 < R) {
  int M1 = (2*L + R) / 3;
  int M2 = (L + 2*R) / 3;
  if (a[M1] <= a[M2]) R = M2;
  else L = M1;
}
int mn = a[L++];
while (L <= R) mn = min(mn, a[L++]);
return mn; // works, but loop is so, yeah

Is there maybe a cleaner way of doing ternary search on arrays without the brute force loop at the end? Like, do I need to tweak the formula for M1 and M2 or something similar?

  • Vote: I like it
  • +24
  • Vote: I do not like it

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Firstly, on a funny note:

What I will give you here is my only code with ternary search on a discrete interval, which is absurdly tedious, just to laugh what one can create if he is very determined :P :

int kl = left_b, kp = right_b, faj = -1, best = 1e18;
while (kl <= kp) {
  int third = (kp - kl) / 3;
  int aktc[] = {kl + third, max(kl + 2 * third, kl + third + (kl < kp))};
  int dis[2];
  REP (wh, 2) {
    Point p = st[tr] + prl * aktc[wh];
    dis[wh] = cent.Dist(p);
  }
  int smaller = 0;
  if (dis[0] < dis[1]) {
    kp = aktc[1] - 1;
  } else {
    smaller = 1;
    kl = aktc[0] + 1;
  }
  if (dis[smaller] < best) {
    faj = aktc[smaller];
    best = dis[smaller];
  }
}

Btw this is version taken from some geo submission, I haven't cleaned it as much as I could have.

Secondly, on a more serious note: We should remember that this 3 is not really needed in that algorithm. We can also set p1=(3*l+2*r)/5 and p2=(2*l+3*r)/5 and it will still work and even will need a bit smaller number of iterations. We just need to have two different points to either cut part on the left of first point or part on the right of second point. In a discrete case much more natural choice would be (l+r)/2 and (l+r)/2 + 1. This way we should be able to come up with cleaner formulas and I will leave that for you as an exercise :P.

→ Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Binary search on a[i+1]-a[i]. http://codeforces.com/blog/entry/11497

→ Reply