Как узнать количество итераций алгоритма двоичного поиска? - PullRequest
Новая
       10

Как узнать количество итераций алгоритма двоичного поиска?

4 голосов
/ 05 мая 2019

Как узнать количество итераций бинарного поиска?

Это мой код: 

int main() 
{
    int target = 11;
    int N = 10;
    std::vector<int> index;
    int num;

    for (int i = 0; i < N; i++) {
        index.push_back(i);
    }

    int counter = 0;
    unsigned int M, L = (unsigned int)-1, R = N;

    M = (R - L) / 2;  // Assume N is not zero

    do {
        int value;
        M = M + L;
        value = index[M];
        if (value < target) L = M; else R = M;
        M = (R - L) / 2;
        counter++;
    } while (M);  // M is the size of the current interval

    std::cout << R << '\n';
    std::cout << "counter: " << counter << '\n';

    system("pause");

    return 0;
}

Я хочу знать количество итераций в зависимости от N.Я знаю, как работает этот алгоритм, но я хочу, чтобы число итераций было представлено математически.

Ответы [ 2 ]

3 голосов
/ 05 мая 2019

Я бы пошел на рекурсивный прирост, используя рекурсивную функцию двоичного поиска. В каждой ветви двоичных проверок просто увеличивайте на единицу, и это будет рекурсивно считать итерации.

Смотрите в прямом эфире здесь 

#include <iostream>
#include <vector>

std::size_t binarySearch(
    const std::vector<int>& arr,        // pass array as non-modifiyable(const ref)
    std::size_t start, std::size_t end, // start and end indexes of the array
    const int target)                   // target to find
{
    if (arr.size() == 1) return arr[0] == target ? 1 : 0; // edge case

    if (start <= end)
    {
        const std::size_t mid_index = start + ((end - start) / 2);
        return arr[mid_index] == target ? 1 :                         // found the middle element
               arr[mid_index] < target ?
                 binarySearch(arr, mid_index + 1, end, target) + 1:   // target is greater than mid-element
                 binarySearch(arr, start, mid_index - 1, target) + 1; // target is less than mid-element
    }
    return 0;
}

int main()
{
    int target = 11;
    const int N = 10;
    std::vector<int> index;
    index.reserve(N); // reserve some memory
    for (int i = 0; i < N; i++) {
        index.push_back(i);
    }
    std::cout << "counter: " << binarySearch(index, 0, index.size() - 1, target) << std::endl;
    return 0;
}

выход 

counter: 4
1 голос
/ 05 мая 2019

Математически Максимально возможная итерация (в предположении, что используется только целочисленный тип) is = ceil (log2 (initial_r - initial_l)) основание журнала равно 2, потому что каждый раз, когда мы делим наш диапазон пополам, беря середину и переключаясь на одно изполовина.

...