Essence: there is an array of elements, and to search for an element in it, you need to apply a ternary search. However, everywhere on the Internet there are only algorithms for the function (and it must first increase and then decrease ) and not a single algorithm for the array ... How can I adapt the algorithm for this case?

  • What is the "ternary search"? What are you talking about? Che did not understand ... What does not suit a simple run through the array and search for the desired item? - BOPOH
  • Oh, there is also an ordered array here, so instead of O (N) you can apply a binary search for O (log N) - BOPOH
  • Not satisfied with the fact that in the condition given exactly the ternary search. And still it is necessary to check how much faster it is of the same binary. - Byulent
  • Then what does the "element search" have to do with it, if you need to look for an extremum? And the array is exactly ordered? If so, what prevents to apply the same ternary search for the search for extremum, setting the boundary conditions so as not to go beyond the array boundaries. Then the search will end exactly when these boundary conditions begin to be violated. The truth is that in this case it is not clear what to look for - maximum or minimum, since there is both. Maybe the original problem is simply formulated in a slightly different way? - BOPOH
  • The task: to determine whether there is an element in the array or not. Repeat 5 times for emails that are, and for emails that are not. Algorithm of search - ternary search (which the teacher called "tertiary") - Byulent

1 answer 1

There is a search option that can be called ternary - this is when the options "less", "equal" and "more" are used (there are such tasks for weighing coins). A similar construction had an IF statement in the Fortran language, when the expression was followed by three labels.

We will express the idea of ​​a ternary search with the help of a nonexistent conventional structure of the form

ift (expr) ? {<} : {=} : {>}.

If the dimension of the array a is less than bb = 2 n , then the algorithm for determining the number of an element in the array can be:

 i=0; for (b=bb/2; b>0; b/=2){ aa = a[i+b]; ift(x - aa) ? {} : {i+=bb; break;} : {i += b;} }

Thus, a ternary search saves one iteration.