Binary Search Vs Ternary Search
Introduction
Binary search and ternary search are two very efficient searching algorithms used to find an element (key) in an array. Both are based on the divide and conquer policy.
In binary search, we keep dividing the sorted array into two halves (and determine which one has the key) until we find the element we’re searching for, whereas, in ternary search, we divide the array into three halves (and determine which one has the key) until we find the element we’re searching for. In this article, we’ll see the difference between these two based on their time complexity.
Before we dive in, let's brush up our skills in Binary Search with the following video.
Analysis of the time complexity
Since in ternary search, we divide our array into three parts and discard the two-thirds of space at iteration each time, you might think that it's time complexity is log3(n) which is faster as compared to that of binary search which has a complexity of log2(n), if the size of the array is n.
But you’re in a delusion if you think so.
Let’s look at the code once to see what exactly is happening.
Implementation of Binary Search
#include <bits/stdc++.h> #define int long long #define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); #define mod 1000000007 using namespace std; int func(int a[],int n,int target){ int low = 0; int high = n-1; while(low<=high){ int mid = low + (high - low) / 2; //mid point that divides the array into two parts //if found, return the index if (a[mid] == target) { return mid; } //if the target is greater than a[mid], means that target lies in the part from 0 to mid // Therefore, move high to mid1-1; else if (a[mid] > target) { high = mid - 1; } //if the target is greater than a[mid], means that target lies in the part from mid to high // Therefore, move low to mid1+1; else if (a[mid] < target) { low = mid + 1; } } return -1; //if an element is not found, return -1. } int32_t main(){ IOS; int n; cin>>n; int a[n]; for(int i=0;i<n;i++){ cin>>a[i]; } int target; cin>>target; int idx = func(a,n,target); if(idx!=-1){ cout<<idx<<endl; } else{ cout<<"Element not found!"<<endl; } } |
Input
4 2 5 6 7 6 |
Output
2 |
Implementation of Ternary Search
#include <bits/stdc++.h> #define int long long #define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); #define mod 1000000007 using namespace std; int func(int a[],int n,int target){ int low = 0; int high = n-1; while(low<=high){ int mid1 = low + (high - low) / 3; //first partition point int mid2 = high - (high - low) / 3; // second partition point //if found, return the index if (a[mid1] == target) { return mid1; } else if (a[mid2] == target) { return mid2; } //if the target is smaller than a[mid1], means that target lies in the part from 0 to mid1 // Therefore, move high to mid1-1; else if (a[mid1] > target) { high = mid1 - 1; } //if the target is greater than a[mid1], means that target lies in the part from mid2 to n-1 // Therefore, move low to mid2+1; else if (a[mid2] < target) { low = mid2 + 1; } //Otherwise target lies in the part from mid1 to mid2 // Therefore, move high to mid2-1 and low to mid1+1; else { low = mid1 + 1, high = mid2 - 1; } } return -1; } int32_t main(){ IOS; int n; cin>>n; int a[n]; for(int i=0;i<n;i++){ cin>>a[i]; } int target; cin>>target; int idx = func(a,n,target); if(idx!=-1){ cout<<idx<<endl; } else{ cout<<"Element not found!"<<endl; } } |
Input
4 2 5 6 7 6 |
Output
2 |
We can observe from the above implementation that, for the array a[] = {2,5,6,8,9,10} and target = 6, in the ternary search,
Iteration 1: Low = 0, high = 5 mid1 = 1, mid2 = 4 Comparison 1: a[mid1] = 5 !=6 (false) Comparison 2: a[mid2] = 9!=6 (false) Comparison 3: a[mid1] > target => 5>6 (false) Comparison 4: a[mid2] <target => 9<6 (false) Here, target>a[mid1] and target<a[mid2], therefore, low = mid1+1 = 2 and high = mid2-1 = 4-1 = 3. We move on to the next comparison. |
Iteration 2: Low = 2, high = 3 mid1 = 2, mid2 = 3 Comparison 1: a[mid1] = 6==6 (true) Return 2. |
Whereas in the case of binary search,
Iteration 1: Low = 0, high = 5 mid= 2 Comparison 1: a[mid] = 6 ==6 (true) Return 2. |
So, ternary search makes 4 comparisons whereas, in binary search, we only make a maximum of 2 comparisons in each iteration.
In binary search, T1(n) = 2clog2(n) + O(1) (c = constant)
In ternary search, T2(n) = 4clog3(n) + O(1) (c=constant)
Thus, T2(n)~2*log3(2) * T1(n), implies that ternary search will make more comparisons and thus will have more time complexity.
Let’s move on to some frequently asked questions on binary search vs ternary search.
Frequently asked questions
- What is the time complexity of ternary search?
The time complexity of ternary search is O(log3 n).
- Is binary search better than ternary search?
Yes, in terms of complexity, binary search is better than ternary search.
- Is ternary search useful?
Ternary search is extremely useful in the case when the function can’t be differentiated easily. We can use it to find the extremum(minimum and maximum) of a function.
- Is linear search better than binary search?
Binary search is more efficient than linear search; it has a time complexity of O(log n). The array must be in a sorted order for it to work.
- What are the different searching algorithms?
Linear search, Binary search and ternary search are the three different searching algorithms.
Key takeaways
In this article, we did the comparison between binary search and ternary search on the basis of their time complexity. If you clearly understood, move forward and learn about the top searching and sorting algorithms used.
These searching algorithms are frequently, very efficient and are asked in various coding contests as well as placements tests.
To practice problems on searching algorithms, Codestudio is a one-stop destination. This platform will help you acquire effective coding techniques and give you an overview of student interview experience in various product-based companies.
Happy Coding!
Comments
No comments yet
Be the first to share what you think