Рубрики

Почему бинарный поиск предпочтительнее троичного поиска?

Ниже приведена простая рекурсивная функция двоичного поиска в C ++, взятая отсюда .

// Рекурсивная функция двоичного поиска. Возвращает местоположение х в
// данный массив arr [l..r] присутствует, иначе -1

int binarySearch(int arr[], int l, int r, int x)

{

   if (r >= l)

   {

        int mid = l + (r - l)/2;

   

        // Если элемент присутствует в самой середине

        if (arr[mid] == x)  return mid;

   

        // Если элемент меньше среднего, он может присутствовать только

        // в левом подмассиве

        if (arr[mid] > x) return binarySearch(arr, l, mid-1, x);

   

        // Иначе элемент может присутствовать только в правом подмассиве

        return binarySearch(arr, mid+1, r, x);

   }

   

   // Мы достигаем здесь, когда элемент отсутствует в массиве

   return -1;

Ниже приведена простая рекурсивная функция троичного поиска :

С

// Рекурсивная троичная функция поиска. Возвращает местоположение х в
// данный массив arr [l..r] присутствует, иначе -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 (arr[mid1] == x)  return mid1;

  

        // Если x присутствует в mid2

        if (arr[mid2] == x)  return mid2;

  

        // Если х присутствует в левой трети

        if (arr[mid1] > x) return ternarySearch(arr, l, mid1-1, x);

  

        // Если х присутствует в правой трети

        if (arr[mid2] < x) return ternarySearch(arr, mid2+1, r, x);

  

        // Если х присутствует в средней трети

        return ternarySearch(arr, mid1+1, mid2-1, x);

   }

   // Мы достигаем здесь, когда элемент отсутствует в массиве

   return -1;

}

Джава

import java.io.*;

  

class GFG

{

public static void main (String[] args) 

{

      
// Рекурсивная троичная функция поиска.
// Возвращает местоположение x в заданном массиве
// присутствует arr [l..r], иначе -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 (arr[mid1] == x)  return mid1;

    

        // Если x присутствует в mid2

        if (arr[mid2] == x)  return mid2;

    

        // Если х присутствует в левой трети

        if (arr[mid1] > x) 

            return ternarySearch(arr, l, mid1 - 1, x);

    

        // Если х присутствует в правой трети

        if (arr[mid2] < x) 

            return ternarySearch(arr, mid2 + 1, r, x);

    

        // Если х присутствует в средней трети

        return ternarySearch(arr, mid1 + 1

                                  mid2 - 1, x);

   }

     

   // Мы достигаем здесь, когда элемент

   // отсутствует в массиве

   return -1;

}
}

python3

# Рекурсивная троичная функция поиска. Возвращает местоположение х в
# данный массив arr [l..r] присутствует, иначе -1

def ternarySearch(arr, l, r, x):

    if (r >= l):

        mid1 = l + (r - l)//3

        mid2 = mid1 + (r - l)//3

   

        # Если х присутствует в середине

        if arr[mid1] == x:

            return mid1

   

        # Если х присутствует в середине 2

        if arr[mid2] == x:

            return mid2

   

        # Если х присутствует в левой трети

        if arr[mid1] > x:

            return ternarySearch(arr, l, mid1-1, x)

   

        # Если х присутствует в правой трети

        if arr[mid2] < x:

            return ternarySearch(arr, mid2+1, r, x)

   

        # Если х присутствует в средней трети

        return ternarySearch(arr, mid1+1, mid2-1, x)

     

    # Мы достигаем здесь, когда элемент не присутствует в массиве

    return -1

     
# Этот код предоставлен ankush_953

    

PHP

<?php
// Рекурсивная троичная функция поиска.
// Возвращает местоположение х в
// данный массив arr [l..r] равен
// присутствует, иначе -1

function ternarySearch($arr, $l

                       $r, $x)

{

    if ($r >= $l)

    {

        $mid1 = $l + ($r - $l) / 3;

        $mid2 = $mid1 + ($r - l) / 3;

  

        // Если х присутствует в середине

        if ($arr[mid1] == $x

            return $mid1;

  

        // Если x присутствует

        // в середине2

        if ($arr[$mid2] == $x

            return $mid2;

  

        // Если х присутствует в

        // осталось треть

        if ($arr[$mid1] > $x

            return ternarySearch($arr, $l

                                 $mid1 - 1, $x);

  

        // Если х присутствует в правой трети

        if ($arr[$mid2] < $x

            return ternarySearch($arr, $mid2 + 1, 

                                         $r, $x);

  

        // Если х присутствует в

        // средняя треть

        return ternarySearch($arr, $mid1 + 1, 

                             $mid2 - 1, $x);

}

  
// Мы достигаем здесь, когда элемент
// нет в массиве

return -1;

}

  
// Этот код предоставлен anuj_67
?>

Что из двух приведенных выше делает меньше сравнений в худшем случае?
На первый взгляд кажется, что троичный поиск делает меньше сравнений, так как он делает Log 3 n рекурсивными вызовами, но двоичный поиск делает Log 2 n рекурсивными вызовами. Давайте посмотрим поближе.
Ниже приведена рекурсивная формула для подсчета сравнений в худшем случае бинарного поиска.

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

Ниже приведена рекурсивная формула для подсчета сравнений в наихудшем случае троичного поиска.

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

В двоичном поиске в худшем случае выполняется сравнение 2Log 2 n + 1. В троичном поиске есть 4Log 3 n + 1 сравнения в худшем случае.

Time Complexity for Binary search = 2clog2n + O(1)
Time Complexity for Ternary search = 4clog3n + O(1)

Поэтому сравнение троичных и двоичных поисков сводится к сравнению выражений 2Log 3 n и Log 2 n. Значение 2Log 3 n можно записать в виде (2 / Log 2 3) * Log 2 n. Поскольку значение (2 / Log 2 3) больше одного, тернарный поиск в худшем случае выполняет больше сравнений, чем бинарный поиск.

Упражнение:
Почему Merge Sort делит входной массив на две половины, а не на три или более частей?

Эта статья предоставлена Anmol . Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой теме

Рекомендуемые посты:

Почему бинарный поиск предпочтительнее троичного поиска?

0.00 (0%) 0 votes