Quelle est la différence entre la recherche linéaire et la recherche binary?

Quelle est la différence entre la recherche linéaire et la recherche binary?

    Une recherche linéaire regarde une liste, un élément à la fois, sans sauter. En termes de complexité, il s’agit d’une recherche O(n) – le temps nécessaire à la recherche dans la liste augmente au même rythme que la liste.

    Une recherche binary est lorsque vous commencez avec le milieu d’une liste sortingée et voyez si cela est supérieur ou inférieur à la valeur que vous recherchez, ce qui détermine si la valeur est dans la première ou la seconde moitié de la liste. Aller à mi-chemin de la sous-liste, et comparer à nouveau, etc. C’est à peu près comme ça que les humains recherchent généralement un mot dans un dictionnaire (bien que nous utilisions de meilleures méthodes heuristiques, évidemment – si vous cherchez “chat” commencer à “M”). En termes de complexité, il s’agit d’une recherche O(log n) – le nombre d’opérations de recherche augmente plus lentement que la liste, car vous réduisez de moitié l’espace de recherche à chaque opération.

    Par exemple, supposons que vous recherchiez U dans une liste de lettres AZ (index 0-25; nous recherchons la valeur à l’index 20).

    Une recherche linéaire demanderait:

    list[0] == 'U' ? Non.
    list[1] == 'U' ? Non.
    list[2] == 'U' ? Non.
    list[3] == 'U' ? Non.
    list[4] == 'U' ? Non.
    list[5] == 'U' ? Non.
    list[20] == 'U' ? Oui. Fini.

    La recherche binary demanderait:

    Comparez la list[12] (‘M’) avec ‘U’: Plus petit, regardez plus loin. (Portée = 13-25)
    Comparez la list[19] (‘T’) avec ‘U’: Plus petite, regardez plus loin. (Portée = 20-25)
    Comparez la list[22] (‘W’) avec ‘U’: plus grande, regardez plus tôt. (Plage = 20-21)
    Comparer la list[20] (‘U’) avec ‘U’: Trouvé! Fini.

    En comparant les deux:

    • La recherche binary nécessite que les données d’entrée soient sortingées; la recherche linéaire ne
    • La recherche binary nécessite une comparaison de commande ; la recherche linéaire ne nécessite que des comparaisons d’égalité
    • La recherche binary a la complexité O (log n); la recherche linéaire a la complexité O (n) comme discuté précédemment
    • La recherche binary nécessite un access aléatoire aux données. la recherche linéaire ne nécessite qu’un access séquentiel (cela peut être très important – cela signifie qu’une recherche linéaire peut diffuser des données de taille arbitraire)

    Considérez-le comme deux manières différentes de trouver votre chemin dans un annuaire téléphonique. Une recherche linéaire commence au début, en lisant chaque nom jusqu’à ce que vous trouviez ce que vous cherchez. Une recherche binary, par contre, est lorsque vous ouvrez le livre (généralement au milieu), regardez le nom en haut de la page et décidez si le nom que vous recherchez est plus grand ou plus petit que celui que vous cherche. Si le nom que vous recherchez est plus grand, alors vous continuez à chercher la partie supérieure du livre de cette façon.

    Une recherche linéaire fonctionne en examinant chaque élément d’une liste de données jusqu’à ce qu’elle trouve la cible ou atteigne la fin. Cela se traduit par une performance O (n) sur une liste donnée. Une recherche binary nécessite que les données soient sortingées. Nous pouvons tirer parti de ces informations pour réduire le nombre d’éléments à examiner pour trouver notre cible. Nous soaps que si nous regardons un élément aléatoire dans les données (disons l’élément intermédiaire) et que cet object est plus grand que notre cible, alors tous les éléments à droite de cet élément seront également plus grands que notre cible. Cela signifie qu’il suffit de regarder la partie gauche des données. Fondamentalement, chaque fois que nous recherchons la cible et que nous manquons, nous pouvons éliminer la moitié des articles restants. Cela nous donne une belle complexité temporelle O (log n).

    Rappelez-vous simplement que le sorting des données, même avec l’algorithme le plus efficace, sera toujours plus lent qu’une recherche linéaire (les algorithmes de sorting les plus rapides sont O (n * log n)). Ainsi, vous ne devez jamais sortinger les données simplement pour effectuer une seule recherche binary ultérieurement. Mais si vous effectuez de nombreuses recherches (par exemple, au moins des recherches O (log n)), il peut être utile de sortinger les données pour pouvoir effectuer des recherches binarys. Vous pouvez également considérer d’autres structures de données telles qu’une table de hachage dans de telles situations.

    Une recherche linéaire commence au début d’une liste de valeurs et vérifie 1 par 1 pour le résultat que vous recherchez.

    Une recherche binary commence au milieu d’un tableau sortingé et détermine quel côté (le cas échéant) la valeur recherchée est activée. Cette “moitié” du tableau est alors à nouveau recherchée de la même manière, divisant les résultats en deux par deux à chaque fois.

    Assurez-vous de décider si le gain de la recherche binary plus rapide vaut le coût de garder la liste sortingée (pour pouvoir utiliser la recherche binary). Par exemple, si vous avez beaucoup d’opérations d’insertion / suppression et que seule une recherche occasionnelle est possible, la recherche binary pourrait être plus lente que la recherche linéaire.

    Essayez ceci: Choisissez un nom aléatoire “Nom, Prénom” et recherchez-le dans votre répertoire.

    1ère fois: commencez au début du livre, lisez les noms jusqu’à ce que vous les trouviez, ou trouvez l’endroit où il se serait produit par ordre alphabétique et notez qu’il n’y est pas.

    2ème fois: ouvrez le livre à mi-parcours et regardez la page. Demandez-vous si cette personne doit être à gauche ou à droite. Quel que soit celui-ci, prenez ce 1/2 et trouvez le milieu. Répétez cette procédure jusqu’à ce que vous trouviez la page sur laquelle l’entrée doit se trouver, puis appliquez le même processus aux colonnes ou effectuez une recherche linéaire sur les noms de la page, comme précédemment.

    Chronométrez les deux méthodes et rapportez!

    [considérez également quelle approche est la meilleure si tout ce que vous avez est une liste de noms, pas sortingée …]

    La recherche linéaire, également appelée recherche séquentielle, examine chaque élément en séquence depuis le début pour voir si l’élément souhaité est présent dans la structure de données. Lorsque la quantité de données est petite, cette recherche est rapide.Il est facile, mais le travail nécessaire est proportionnel à la quantité de données à rechercher. Doubler le nombre d’éléments doublera le temps de recherche si l’élément souhaité n’est pas présent.

    La recherche binary est efficace pour un plus grand tableau. En cela, nous vérifions l’élément du milieu. Si la valeur est supérieure à celle que nous recherchons, alors regardez dans la première moitié, sinon regardez dans la seconde moitié. Répétez cette opération jusqu’à ce que l’élément souhaité soit trouvé. La table doit être sortingée pour la recherche binary. Il élimine la moitié des données à chaque itération. Son logarithmique.

    Si nous avons 1000 éléments à rechercher, la recherche binary prend environ 10 étapes, la recherche linéaire 1000 étapes.

    la recherche binary s’exécute en temps O (logn) alors que la recherche linéaire s’exécute en temps O (n), ainsi la recherche binary a de meilleures performances

    Une recherche linéaire regarde une liste, un élément à la fois, sans sauter. En termes de complexité, il s’agit d’une recherche O (n) – le temps nécessaire à la recherche dans la liste augmente au même rythme que la liste.

    Une recherche binary est lorsque vous commencez avec le milieu d’une liste sortingée et voyez si cela est supérieur ou inférieur à la valeur que vous recherchez, ce qui détermine si la valeur est dans la première ou la seconde moitié de la liste. Aller à mi-chemin de la sous-liste, et comparer à nouveau, etc. C’est à peu près comme ça que les humains recherchent généralement un mot dans un dictionnaire (bien que nous utilisions de meilleures méthodes heuristiques, évidemment – si vous cherchez “chat” commencer à “M”). En termes de complexité, il s’agit d’une recherche O (log n) – le nombre d’opérations de recherche augmente plus lentement que la liste, car vous réduisez de moitié l’espace de recherche à chaque opération.

    Linear Search parcourt les éléments jusqu’à ce qu’elle trouve la valeur recherchée.

    Efficacité: O(n)

    Exemple de code Python:

     test_list = [1, 3, 9, 11, 15, 19, 29] test_val1 = 25 test_val2 = 15 def linear_search(input_array, search_value): index = 0 while (index < len(input_array)) and (input_array[index] < search_value): index += 1 if index >= len(input_array) or input_array[index] != search_value: return -1 return index print linear_search(test_list, test_val1) print linear_search(test_list, test_val2) 

    Binary Search trouve l’élément central du tableau. Vérifie que la valeur moyenne est supérieure ou inférieure à la valeur de recherche. S’il est plus petit, il obtient le côté gauche du tableau et trouve l’élément central de cette partie. S’il est plus grand, récupère la partie droite du tableau. Il boucle l’opération jusqu’à ce qu’il trouve la valeur recherchée. Ou s’il n’y a pas de valeur dans le tableau termine la recherche.

    Efficacité: O(logn)

    Exemple de code Python:

     test_list = [1, 3, 9, 11, 15, 19, 29] test_val1 = 25 test_val2 = 15 def binary_search(input_array, value): low = 0 high = len(input_array) - 1 while low <= high: mid = (low + high) / 2 if input_array[mid] == value: return mid elif input_array[mid] < value: low = mid + 1 else: high = mid - 1 return -1 print binary_search(test_list, test_val1) print binary_search(test_list, test_val2) 

    Vous pouvez également voir des informations visualisées sur Linear and Binary Search ici: https://www.cs.usfca.edu/~galles/visualization/Search.html

    Pour une compréhension claire, veuillez jeter un coup d’œil à mes implémentations de codepen https://codepen.io/serdarsenay/pen/XELWqN

    La plus grande différence est la nécessité de sortinger votre échantillon avant d’appliquer une recherche binary; par conséquent, pour la plupart des échantillons de «taille normale» (ce qui signifie que l’on doit argumenter), la recherche sera plus rapide avec un algorithme de recherche linéaire.

    Voici le code javascript, pour html et css et un exemple complet, veuillez vous reporter au lien codepen ci-dessus.

     var unsortedhaystack = []; var haystack = []; function init() { unsortedhaystack = document.getElementById("haystack").value.split(' '); } function sortHaystack() { var t = timer('sort benchmark'); haystack = unsortedhaystack.sort(); t.stop(); } var timer = function(name) { var start = new Date(); return { stop: function() { var end = new Date(); var time = end.getTime() - start.getTime(); console.log('Timer:', name, 'finished in', time, 'ms'); } } }; function lineerSearch() { init(); var t = timer('lineerSearch benchmark'); var input = this.event.target.value; for(var i = 0;i input) { lastIndex = currentIndex - 1; //console.log(currentIndex + " substracted, fI:"+firstIndex+", lI: "+lastIndex); } else { document.getElementById('result').innerHTML = 'result is... "' + haystack[currentIndex] + '", on index: ' + currentIndex + ' of the sorted array. Found' + ' within ' + iterations + ' iterations'; console.log(document.getElementById('result').innerHTML); t.stop(); return true; } } }