Рубрики

Алгоритмы | Поиск | вопрос 2

Что из следующего является правильным повторением для худшего случая бинарного поиска?
(A) T (n) = 2T (n / 2) + O (1) и T (1) = T (0) = O (1)
(B) T (n) = T (n-1) + O (1) и T (1) = T (0) = O (1)
(C) T (n) = T (n / 2) + O (1) и T (1) = T (0) = O (1)
(D) T (n) = T (n-2) + O (1) и T (1) = T (0) = O (1)

Ответ: (с)
Пояснение: Ниже приводится типичная реализация бинарного поиска.

// Ищет x в arr [low..high]. Если x присутствует, то возвращает его индекс, иначе -1

int binarySearch(int arr[], int low, int high, int x)

{

    if(high >= low)

    {

        int mid = low + (high - low)/2;

        if (x == arr[mid])

            return mid;

        if (x> arr[mid])

            return binarySearch(arr, (mid + 1), high);

        else

            return binarySearch(arr, low, (mid -1));

    }

  

    return -1;

}

В двоичном поиске мы сначала сравниваем данный элемент x с серединой массива. Если x соответствует среднему элементу, мы возвращаем средний индекс. В противном случае мы либо возвращаемся к левой половине массива, либо к правой половине массива.

Таким образом, повторение T (n) = T (n / 2) + O (1)
Тест на этот вопрос

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

Алгоритмы | Поиск | вопрос 2

0.00 (0%) 0 votes