Why is Binary Search preferred over Ternary Search?

Last Updated : 19 Jan, 2023

The following is a simple recursive Binary Search function in C++ taken from here.

C++

// CPP program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
 
// A recursive binary search function. It returns location of x in
// given array arr[l..r] is present, otherwise -1
int binarySearch(int arr[], int l, int r, int x)
{
   if (r >= l)
   {
        int mid = l + (r - l)/2;
   
        // If the element is present at the middle itself
        if (arr[mid] == x)  return mid;
   
        // If element is smaller than mid, then it can only be present
        // in left subarray
        if (arr[mid] > x) return binarySearch(arr, l, mid-1, x);
   
        // Else the element can only be present in right subarray
        return binarySearch(arr, mid+1, r, x);
   }
   
   // We reach here when element is not present in array
   return -1;
}
 
// This code is contributed by sanjoy_62.

C

// A recursive binary search function. It returns location of x in
// given array arr[l..r] is present, otherwise -1
int binarySearch(int arr[], int l, int r, int x)
{
   if (r >= l)
   {
        int mid = l + (r - l)/2;
  
        // If the element is present at the middle itself
        if (arr[mid] == x)  return mid;
  
        // If element is smaller than mid, then it can only be present
        // in left subarray
        if (arr[mid] > x) return binarySearch(arr, l, mid-1, x);
  
        // Else the element can only be present in right subarray
        return binarySearch(arr, mid+1, r, x);
   }
  
   // We reach here when element is not present in array
   return -1;
} 

Java

// A recursive binary search function. It returns location of x in
// given array arr[l..r] is present, otherwise -1
static int binarySearch(int arr[], int l, int r, int x)
{
   if (r >= l)
   {
        int mid = l + (r - l)/2;
  
        // If the element is present at the middle itself
        if (arr[mid] == x)  return mid;
  
        // If element is smaller than mid, then it can only be present
        // in left subarray
        if (arr[mid] > x) return binarySearch(arr, l, mid-1, x);
  
        // Else the element can only be present in right subarray
        return binarySearch(arr, mid+1, r, x);
   }
  
   // We reach here when element is not present in array
   return -1;
} 
 
// This code is contributed by gauravrajput1 

Python3

# A recursive binary search function. It returns location of x in
# given array arr[l..r] is present, otherwise -1
def binarySearch(arr, l, r, x):
   if (r >= l):
        mid = l + (r - l)/2;
         
   # If the element is present at the middle itself
   if (arr[mid] == x): 
        return mid;
       
   # If element is smaller than mid, then it can only be present
   # in left subarray
    if (arr[mid] > x): 
    return binarySearch(arr, l, mid-1, x);
   
    # Else the element can only be present in right subarray
    return binarySearch(arr, mid+1, r, x);
    
 # We reach here when element is not present in array
   return -1;
  
# This code is contributed by umadevi9616

C#

// A recursive binary search function. It returns location of x in
// given array arr[l..r] is present, otherwise -1
static int binarySearch(int []arr, int l, int r, int x)
{
   if (r >= l)
   {
        int mid = l + (r - l)/2;
  
        // If the element is present at the middle itself
        if (arr[mid] == x)  return mid;
  
        // If element is smaller than mid, then it can only be present
        // in left subarray
        if (arr[mid] > x) return binarySearch(arr, l, mid-1, x);
  
        // Else the element can only be present in right subarray
        return binarySearch(arr, mid+1, r, x);
   }
  
   // We reach here when element is not present in array
   return -1;
} 
 
// This code is contributed by gauravrajput1

Javascript

<script>
// A recursive binary search function. It returns location of x in
// given array arr[l..r] is present, otherwise -1
function binarySearch(arr , l , r , x)
{
   if (r >= l)
   {
        var mid = l + (r - l)/2;
  
        // If the element is present at the middle itself
        if (arr[mid] == x)  return mid;
  
        // If element is smaller than mid, then it can only be present
        // in left subarray
        if (arr[mid] > x) return binarySearch(arr, l, mid-1, x);
  
        // Else the element can only be present in right subarray
        return binarySearch(arr, mid+1, r, x);
   }
  
   // We reach here when element is not present in array
   return -1;
} 
 
// This code is contributed by gauravrajput1 
</script>

The following is a simple recursive Ternary Search function :

C++

// A recursive ternary search function. It returns location of x in
// given array arr[l..r] is present, otherwise -1
int ternarySearch(int arr[], int l, int r, int x)
{
   if (r >= l)
   {
        int mid1 = l + (r - l)/3;
        int mid2 = mid1 + (r - l)/3;
 
        // If x is present at the mid1
        if (arr[mid1] == x)  return mid1;
 
        // If x is present at the mid2
        if (arr[mid2] == x)  return mid2;
 
        // If x is present in left one-third
        if (arr[mid1] > x) return ternarySearch(arr, l, mid1-1, x);
 
        // If x is present in right one-third
        if (arr[mid2] < x) return ternarySearch(arr, mid2+1, r, x);
 
        // If x is present in middle one-third
        return ternarySearch(arr, mid1+1, mid2-1, x);
   }
   // We reach here when element is not present in array
   return -1;
}

C

// A recursive ternary search function. It returns location of x in
// given array arr[l..r] is present, otherwise -1
int ternarySearch(int arr[], int l, int r, int x)
{
   if (r >= l)
   {
        int mid1 = l + (r - l)/3;
        int mid2 = mid1 + (r - l)/3;
 
        // If x is present at the mid1
        if (arr[mid1] == x)  return mid1;
 
        // If x is present at the mid2
        if (arr[mid2] == x)  return mid2;
 
        // If x is present in left one-third
        if (arr[mid1] > x) return ternarySearch(arr, l, mid1-1, x);
 
        // If x is present in right one-third
        if (arr[mid2] < x) return ternarySearch(arr, mid2+1, r, x);
 
        // If x is present in middle one-third
        return ternarySearch(arr, mid1+1, mid2-1, x);
   }
   // We reach here when element is not present in array
   return -1;
}

Java

import java.io.*;
 
class GFG
{
public static void main (String[] args) 
{
     
// A recursive ternary search function. 
// It returns location of x in given array
// arr[l..r] is present, otherwise -1
static int ternarySearch(int arr[], int l, 
                         int r, int x)
{
   if (r >= l)
   {
        int mid1 = l + (r - l) / 3;
        int mid2 = mid1 + (r - l) / 3;
   
        // If x is present at the mid1
        if (arr[mid1] == x)  return mid1;
   
        // If x is present at the mid2
        if (arr[mid2] == x)  return mid2;
   
        // If x is present in left one-third
        if (arr[mid1] > x) 
            return ternarySearch(arr, l, mid1 - 1, x);
   
        // If x is present in right one-third
        if (arr[mid2] < x) 
            return ternarySearch(arr, mid2 + 1, r, x);
   
        // If x is present in middle one-third
        return ternarySearch(arr, mid1 + 1, 
                                  mid2 - 1, x);
   }
    
   // We reach here when element is
   // not present in array
   return -1;
}
}

Python3

# A recursive ternary search function. It returns location of x in
# given array arr[l..r] is present, otherwise -1
def ternarySearch(arr, l, r, x):
    if (r >= l):
        mid1 = l + (r - l)//3
        mid2 = mid1 + (r - l)//3
  
        # If x is present at the mid1
        if arr[mid1] == x:
            return mid1
  
        # If x is present at the mid2
        if arr[mid2] == x:
            return mid2
  
        # If x is present in left one-third
        if arr[mid1] > x:
            return ternarySearch(arr, l, mid1-1, x)
  
        # If x is present in right one-third
        if arr[mid2] < x:
            return ternarySearch(arr, mid2+1, r, x)
  
        # If x is present in middle one-third
        return ternarySearch(arr, mid1+1, mid2-1, x)
    
    # We reach here when element is not present in array
    return -1
    
# This code is contributed by ankush_953
   

C#

     
// A recursive ternary search function. 
// It returns location of x in given array
// arr[l..r] is present, otherwise -1
static int ternarySearch(int []arr, int l, 
                         int r, int x)
{
   if (r >= l)
   {
        int mid1 = l + (r - l) / 3;
        int mid2 = mid1 + (r - l) / 3;
   
        // If x is present at the mid1
        if (arr[mid1] == x)  return mid1;
   
        // If x is present at the mid2
        if (arr[mid2] == x)  return mid2;
   
        // If x is present in left one-third
        if (arr[mid1] > x) 
            return ternarySearch(arr, l, mid1 - 1, x);
   
        // If x is present in right one-third
        if (arr[mid2] < x) 
            return ternarySearch(arr, mid2 + 1, r, x);
   
        // If x is present in middle one-third
        return ternarySearch(arr, mid1 + 1, 
                                  mid2 - 1, x);
   }
    
   // We reach here when element is
   // not present in array
   return -1;
}
 
// This code is contributed by gauravrajput1

PHP

<?php
// A recursive ternary search function. 
// It returns location of x in
// given array arr[l..r] is 
// present, otherwise -1
function ternarySearch($arr, $l, 
                       $r, $x)
{
    if ($r >= $l)
    {
        $mid1 = $l + ($r - $l) / 3;
        $mid2 = $mid1 + ($r - l) / 3;
 
        // If x is present at the mid1
        if ($arr[mid1] == $x) 
            return $mid1;
 
        // If x is present 
        // at the mid2
        if ($arr[$mid2] == $x) 
            return $mid2;
 
        // If x is present in 
        // left one-third
        if ($arr[$mid1] > $x) 
            return ternarySearch($arr, $l, 
                                 $mid1 - 1, $x);
 
        // If x is present in right one-third
        if ($arr[$mid2] < $x) 
            return ternarySearch($arr, $mid2 + 1, 
                                         $r, $x);
 
        // If x is present in
        // middle one-third
        return ternarySearch($arr, $mid1 + 1, 
                             $mid2 - 1, $x);
}
 
// We reach here when element
// is not present in array
return -1;
}
 
// This code is contributed by anuj_67
?>

Javascript

<script>
 
    // A recursive ternary search function.
    // It returns location of x in given array
    // arr[l..r] is present, otherwise -1
    function ternarySearch(arr , l , r , x) {
        if (r >= l) {
            var mid1 = l + parseInt((r - l) / 3);
            var mid2 = mid1 + parseInt((r - l) / 3);
 
            // If x is present at the mid1
            if (arr[mid1] == x)
                return mid1;
 
            // If x is present at the mid2
            if (arr[mid2] == x)
                return mid2;
 
            // If x is present in left one-third
            if (arr[mid1] > x)
                return ternarySearch(arr, l, mid1 - 1, x);
 
            // If x is present in right one-third
            if (arr[mid2] < x)
                return ternarySearch(arr, mid2 + 1, r, x);
 
            // If x is present in middle one-third
            return ternarySearch(arr, mid1 + 1, mid2 - 1, x);
        }
 
        // We reach here when element is
        // not present in array
        return -1;
 
// This code is contributed by gauravrajput1
</script>

Which of the above two does less comparisons in worst case?
From the first look, it seems the ternary search does less number of comparisons as it makes Log₃n recursive calls, but binary search makes Log₂n recursive calls. Let us take a closer look.
The following is recursive formula for counting comparisons in worst case of Binary Search.

   T(n) = T(n/2) + 2,  T(1) = 1

The following is recursive formula for counting comparisons in worst case of Ternary Search.

   T(n) = T(n/3) + 4, T(1) = 1

In binary search, there are 2Log₂n + 1 comparisons in worst case. In ternary search, there are 4Log₃n + 1 comparisons in worst case.

Time Complexity for Binary search = 2clog₂n + O(1)
Time Complexity for Ternary search = 4clog₃n + O(1)

Therefore, the comparison of Ternary and Binary Searches boils down the comparison of expressions 2Log₃n and Log₂n . The value of 2Log₃n can be written as (2 / Log₂3) * Log₂n . Since the value of (2 / Log₂3) is more than one, Ternary Search does more comparisons than Binary Search in worst case.
Exercise:
Why Merge Sort divides input array in two halves, why not in three or more parts?

Anmol

Improve

Interpolation search vs Binary search

Is Sentinel Linear Search better than normal Linear Search?

Most Common Searching Algorithms

Other Searching Algorithms

Comparisons between Searching Algorithms

Library implementations of Searching algorithms

Easy problems on Searching algorithms

Medium problems on Searching algorithms

Hard problems on Searching algorithms

Why is Binary Search preferred over Ternary Search?

C++

C

Java

Python3

C#

Javascript

C++

C

Java

Python3

C#

PHP

Javascript

Please Login to comment...

Similar Reads

What kind of Experience do you want to share?