What is ternary Search


#1

How is ternary search different from binary search?


#2

In ternary search we divide domain in three parts
LeftThird := (left2+right)/3
RightThird := (left+right
2)/3
Mid= (left+right)/2

Binary search also we divide in three part
left:=0
mid:= (left+right)/2
right:=n

Binary search is good using over ternary search as it has time complexity (worst case) is T(n)= O(log2(n))


#3

can you please take an example of 6 numbers like if numbers come in the order 3,12,9,2,8,5
how the tree genreated will be different in both the cases,


#4

For Binary search – T(n) = 2clog2n + O(1)
For Ternary search – T(n) = 4clog3n + O(1)
It can be easily established that the time taken by Ternary search is equal to 2log32 times the time taken Binary search algorithm.
Hence we can conclude that binary search is faster than ternary search.


#5

Like linear search and binary search, ternary search is a searching technique that is used to determine the position of a specific value in an array. In binary search, the sorted array is divided into two parts while in ternary search, it is divided into 3 parts and then you determine in which part the element exists.

Ternary search, like binary search, is a divide-and-conquer algorithm. It is mandatory for the array (in which you will search for an element) to be sorted before you begin the search. In this search, after each iteration it neglects

⅓ part of the array and repeats the same operations on the remaining

⅔.
Both have constant space, but big O time for Ternary Search is Log_3 N instead of Binary Search’s Log_2 N which both come out to log(N) since log_b(N) = log_x(N)/log_x(b).

In practice Ternary Search isn’t used because you have to do an extra comparison at each step, which in the general case leads to more comparisons overall.


#6

The last line need a bit more explanation,also can u please elaborate with a simple example of 6 elements how it leads to more comparision.

==>In practice Ternary Search isn’t used because you have to do an extra comparison at each step, which in the general case leads to more comparisons overall.

Also where d in which usecase ternary search is preferred over other searches like binary.


#7

A ternary search algorithm is a technique in computer science for finding the minimum or maximum of a unimodal function. A ternary 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 third.


#8

Ternary search is nothing but a searching technique that is used to determine the position of a specific value in an array.in ternary search the sorted array is divided in to three parts and then you determine in which part the element exits .it’s like a divide and conquer algorithm
Implementation

Int ternary _search(int 1,int r,int x)
{
If(r>=1)
{
Int mid1=1+(r-1)/3;
Int mid2=r-(r-1)/3;
If(at[mid2]==x)
return Mid2;
If (x<ar[mid1])
return ternary _search(1,mid1-1,x);
else if(x>ar[mid2])
return ternary _search(mid2+1,r,x);
else
return ternary_search(mid 1+1,mid2-1,x)
}
return -1;
}