Loading…
Loading…
Splits the range into thirds with two probes per round — asymptotically the same as binary search, but with more comparisons.
Looking for 53. Ternary search keeps two probes instead of one, splitting the live range into thirds.
Tip: click any bar to make it the target.
1int ternarySearch(int[] a, int target) {2 int lo = 0, hi = a.length - 1;3 while (lo <= hi) {4 int third = (hi - lo) / 3;5 int m1 = lo + third, m2 = hi - third;6 if (a[m1] == target) return m1;7 if (a[m2] == target) return m2;8 if (target < a[m1]) hi = m1 - 1;9 else if (target > a[m2]) lo = m2 + 1;10 else { lo = m1 + 1; hi = m2 - 1; } // middle third11 }12 return -1;13}