5
votes

Comment trouver le nombre d'itérations de l'algorithme de recherche binaire?

Comment puis-je obtenir le nombre d'itérations de la recherche binaire?

Voici mon code:

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;
}

Je veux connaître le nombre d'itérations en fonction de N Je sais comment fonctionne cet algorithme mais je veux que le nombre d'itérations soit représenté mathématiquement.

algorithm c++ c++11 binary-search

1 commentaires

Puisque vous savez comment fonctionne l'algorithme, vous savez que chaque itération divise par deux la zone de recherche. Vous pouvez effectuer des divisions successives jusqu'à atteindre une zone de recherche de 1 avec une variété d'entrées N, tracer le N par rapport au nombre d'itérations et choisir la courbe qui convient le mieux, ou vous pouvez court-circuiter l'étape d'ajustement de courbe en sachant déjà quelle opération mathématique effectue des divisions successives

3 Réponses :

3
votes

J'irais pour un incrément récursif en utilisant une fonction de recherche binaire récursive. Dans chaque branche des vérifications binaires, incrémentez simplement de un et cela comptera les itérations de manière récursive.

Voir en direct ici

counter: 4

Sortie :

#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;
}

0 commentaires

2
votes

Mathématiquement, l'itération maximale possible (en supposant que le cas ne soit de type entier) est = ceil (log2 (initial_r - initial_l)) base de log est 2 parce que chaque fois que nous plongeons notre gamme de moitié en prenant un milieu et en passant à l'un des moitiés.

1 commentaires

Pourriez-vous élaborer l'idée avec un exemple, si possible?

0
votes

J'ai également essayé de comprendre la conceptualisation logarithmique, et c'est ainsi que j'essaie de comprendre la réponse

Depuis https://en.wikipedia.org/wiki/Binary_search_algorithm

En mathématiques, le logarithme binaire (log ₂ n) est la puissance à laquelle le nombre 2 doit être élevé pour obtenir la valeur n. Autrement dit, pour tout nombre réel x,
x = log ₂ n <= équivalent à => 2 ^x = n

Chaque arbre binaire à n feuilles a une hauteur d'au moins log ₂ n, avec une égalité lorsque n est une puissance> de deux et que l'arbre est un arbre binaire complet.

La recherche binaire est un peu comme marcher dans un arbre de recherche binaire et diviser par deux les nœuds, et cette série est une série logarithmique (base 2) _{(ma propre compréhension, aucune citation, peut être erronée)}

Et puis sur https://www.cct.lsu.edu/~sidhanti/tutorials/data_structures/page305.html

un arbre binaire parfait de hauteur h a exactement 2 ^{h + 1} -1 nœuds internes. Inversement, la hauteur d'un arbre binaire parfait à n nœuds internes est log ₂ (n + 1). Si nous avons un arbre de recherche qui a la forme d'un arbre binaire parfait, alors chaque recherche infructueuse visite exactement h + 1 nœuds internes, où h = log ₂ (n + 1).

_{(encore une fois avec ma propre compréhension ...)}
Donc, pour atteindre un nœud N (avec la valeur N selon l'arbre de recherche binaire?), Vous feriez des itérations log ₂ (N + 1) (traversez autant de niveaux dans l'arbre) dans le pire des cas (la recherche est toujours une probabilité, donc «pire des cas»).

Essai à sec ici (en construisant un petit BST et en comptant manuellement): https://www.cs.usfca.edu/~galles/visualization/BST.html

_{(réponse ouverte pour révision / confirmations / corrections dans la formulation / calculs aussi bien sûr que j'essaie de consolider différentes ressources pour arriver à une théorie qui a du sens dans ce contexte)}

0 commentaires