Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
In mathematics, the maximum and minimum of a function, known collectively as extrema , are the largest and smallest value that the function takes at a point either within a given neighborhood or on the function domain in its entirety .More generally, the...
In mathematics, a function associates one quantity, the argument of the function, also known as the input, with another quantity, the value of the function, also known as the output. A function assigns exactly one output to each input. The argument and the value may be real numbers, but they can...
that is either strictly increasing and then strictly decreasing or vice versa). A ternary
Ternary
Ternary is an adjective meaning "composed of three items". It can refer to:* Ternary complex, a complex formed by the interaction of three molecules* Ternary compound, a type of chemical compound...
search determines either that the minimum or maximum cannot be in the first third of the domain or that it cannot be in the last third of the domain, then repeats on the remaining two-thirds. A ternary search is an example of a divide and conquer algorithm
Divide and conquer algorithm
In computer science, divide and conquer is an important algorithm design paradigm based on multi-branched recursion. A divide and conquer algorithm works by recursively breaking down a problem into two or more sub-problems of the same type, until these become simple enough to be solved directly...
In computer science, a search algorithm is an algorithm for finding an item with specified properties among a collection of items. The items may be stored individually as records in a database; or may be elements of a search space defined by a mathematical formula or procedure, such as the roots...
).
The function
Assume we are looking for a maximum of f(x) and that we know the maximum lies somewhere between A and B. For the algorithm to be applicable, there must be some value x such that
for all a,b with A ≤ a < b ≤ x, we have f(a) < f(b), and
for all a,b with x ≤ a < b ≤ B, we have f(a) > f(b).
Algorithm
Let a unimodal function f(x) on some interval [l; r]. Take any two points m1 and m2 in this segment: l < m1 < m2 < r. Then there are three possibilities:
if f(m1) < f(m2), then the required maximum can not be located on the left side - [l; m1]. It means that the maximum further makes sense to look only in the interval [m1;r]
if f(m1) > f(m2), that the situation is similar to the previous, up to symmetry. Now, the required maximum can not be in the right side - [m2; r], so go to the segment [l; m2]
if f(m1) = f(m2), than the search should be conducted in [m1; m2], but this case can be attributed to any of the previous two (in order to simplify the code). Sooner or later the length of the segment will be a little less than a predetermined constant, and the process can be stopped.
choice points m1 and m2:
m1 = l + (r-l)/3
m2 = r - (r-l)/3
Recursive algorithm
def ternarySearch(f, left, right, absolutePrecision):
#left and right are the current bounds; the maximum is between them
if (right - left) < absolutePrecision:
return (left + right)/2
In mathematics, Newton's method is an iterative method for finding roots of equations. More generally, Newton's method is used to find critical points of differentiable functions, which are the zeros of the derivative function.-Method:...
(can be used to search for where the derivative is zero)
The golden section search is a technique for finding the extremum of a unimodal function by successively narrowing the range of values inside which the extremum is known to exist. The technique derives its name from the fact that the algorithm maintains the function values for triples of points...
(similar to ternary search, useful if evaluating f takes most of the time per iteration)
Interpolation search is an algorithm for searching for a given key value in an indexed array that has been ordered by the values of the key. It parallels how humans search through a telephone book for a particular name, the key value by which the book's entries are ordered...
In computer science, linear search or sequential search is a method for finding a particular value in a list, that consists of checking every one of its elements, one at a time and in sequence, until the desired one is found....
The source of this article is wikipedia, the free encyclopedia. The text of this article is licensed under the GFDL.
