java - From Binary Search to 3-ary Search -

the reason because 3-ary search less convenient binary search because @ every call 3-ary search needs 2 confronts, while binary search one: 3-ary costs 2log₃(n) , binary log₂(n). known fact.

i had idea.

there algorithm called ternary search allows find maximum of function f upon array, provided maximum one. below java code:

    public static <t> int ternarysearch(t[] array, function<t,double> f){         int l = 0, r = array.length,                 m1 = l + (r-l)/3,                 m2 = r - (r-l)/3,                 valutation;         while( m1 != m2 )             {             valutation = f.apply(array[m1]).compareto(f.apply(array[m2]));             switch(valutation)                 {                 case -1:    {   r = m1;                 m1 = l + (r-l)/3;   m2 = r - (r-l)/3;   break;  }                 case  0:    {   l = m1;     r = m2;     m1 = l + (r-l)/3;   m2 = r - (r-l)/3;   break;  }                 case  1:    {   l = m2;                 m1 = l + (r-l)/3;   m2 = r - (r-l)/3;   break;  }                 }             }                return m1;     } 

if can find function has maximum choosen key , if method compareto() costs one confront between numbers, call of ternarysearch(array, f) costs log₃(n): less binary search.

now, questions are:

1. how can choose such function f?
2. does method compareto() cost one confront between numbers?
3. is idea correct?

answers:

1. just use identity function f(x) = x simplify things - trying find functions best fit values reduce applicability of search lot; identity function , not decreasing values (sorted) array starting point
2. no, costs 2 (see below)
3. i don't think so, reasons listed below:

here few pointers:

• ternary search has potential filter more numbers out (2/3 out instead of 1/2) 1/3 of time (and 2/3 of time filters 1/3rd of space) , indeed require 1 more comparison binary search when using integer.compareto().
  please check source code integer.compareto() see 2 comparisons happening.
• following train of thought, should going n achieve n-ary searches performing better binary search diminishing returns growing ns number of comparisons n
• please see few answers on to similar question on cs stack exchange