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 2log3(n) , binary log2(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 log3(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

Comments

Popular posts from this blog

get url and add instance to a model with prefilled foreign key :django admin -

css - Make div keyboard-scrollable in jQuery Mobile? -

ruby on rails - Seeing duplicate requests handled with Unicorn -