evandrix's blog

By evandrix, 11 years ago, In English

Ternary Search

This search finds the min or max in an array that is either strictly increasing and then decreasing or strictly decreasing then stricly increasing.

//array, left bound, right bound, abs(precision) value for array
int ternarySearch(int data[], int left, int right, int precval){
    if (right - left < precval )
       return (left + right)/2;
   
    //Variable to store first 1/3 of array
    int first_third = ( left * 2 + right ) / 3;
    //Variable to store last 1/3 of array
    int last_third = ( left + right * 2 ) / 3;
   
    if (data[first_third] < data[last_third])
        return ternarySearch(data, first_third, right, precval);
    else
        return ternarySearch(data, left, last_third, precval);      
}
  • Vote: I like it
  • +9
  • Vote: I do not like it

»
11 years ago, # |
  Vote: I like it +22 Vote: I do not like it

Keep up the good work even if people downvote !

  • »
    »
    11 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    thanks, i'm compiling notes for myself to improve