{"id":2374,"date":"2019-12-08T23:26:56","date_gmt":"2019-12-08T20:26:56","guid":{"rendered":"http:\/\/demensdeum.com\/blog\/?p=2374"},"modified":"2024-12-16T22:32:32","modified_gmt":"2024-12-16T19:32:32","slug":"binary-search","status":"publish","type":"post","link":"https:\/\/demensdeum.com\/blog\/fr\/2019\/12\/08\/binary-search\/","title":{"rendered":"Recherche binaire"},"content":{"rendered":"

Supposons que nous ayons besoin de savoir si l’adresse e-mail \u00ab\u00a0demensdeum@gmail.com<\/a>\u00a0\u00bb est incluse dans la liste des adresses e-mail autoris\u00e9es pour la r\u00e9ception de lettres. .<\/p>\n

Parcourons toute la liste du premier au dernier \u00e9l\u00e9ment, en v\u00e9rifiant si l’\u00e9l\u00e9ment est \u00e9gal \u00e0 l’adresse sp\u00e9cifi\u00e9e – Impl\u00e9mentons un algorithme de recherche lin\u00e9aire. Mais cela prendra beaucoup de temps, n’est-ce pas\u00a0?<\/p>\n

Pour r\u00e9pondre \u00e0 cette question, utilisez la notation \u00ab Complexit\u00e9 temporelle des algorithmes \u00bb, \u00ab O \u00bb. Le temps de fonctionnement de la recherche lin\u00e9aire dans le pire des cas est \u00e9gal au ni\u00e8me nombre d’\u00e9l\u00e9ments du tableau, \u00e9crivons cela en notation \u00ab O \u00bb – Sur). Ensuite, nous devons expliquer que pour tout algorithme connu, il existe trois indicateurs de performance : temps d’ex\u00e9cution dans le meilleur des cas, le pire des cas et la moyenne. Par exemple, l’adresse mail \u00ab demensdeum@gmail.com<\/a> \u00bb est dans le premier index du tableau, elle sera alors trouv\u00e9e dans la premi\u00e8re \u00e9tape de l’algorithme, il s’ensuit que le temps d’ex\u00e9cution est au mieux – O(1); et si \u00e0 la fin de la liste, alors c’est le pire des cas – O(n)<\/p>\n

\"\"<\/a><\/p>\n

Mais qu’en est-il des d\u00e9tails de la mise en \u0153uvre logicielle et des performances mat\u00e9rielles\u00a0? Ils devraient influencer Big O\u00a0? Maintenant, respirez et imaginez que le calcul de la complexit\u00e9 temporelle soit calcul\u00e9 pour une machine id\u00e9ale abstraite, dans laquelle il n’y a que cet algorithme et rien d’autre.<\/p>\n

Algorithme<\/h3>\n

Ok, il s’av\u00e8re que la recherche lin\u00e9aire est assez lente, essayons d’utiliser la recherche binaire. Pour commencer, il convient de pr\u00e9ciser que nous ne travaillerons pas avec des donn\u00e9es binaires ; ce nom a \u00e9t\u00e9 donn\u00e9 \u00e0 cette m\u00e9thode en raison des particularit\u00e9s de son travail. Initialement, nous trions le tableau en ordre lexicographique<\/a>, puis l’algorithme prend la plage de l’ensemble du tableau, obtient l’\u00e9l\u00e9ment central de la plage, le compare lexicographiquement<\/a>, et en fonction du r\u00e9sultat de la comparaison, d\u00e9cide quelle plage utiliser pour poursuivre la recherche – la moiti\u00e9 sup\u00e9rieure du courant ou la moiti\u00e9 inf\u00e9rieure. Autrement dit, \u00e0 chaque \u00e9tape de recherche, une d\u00e9cision est prise parmi deux options possibles\u00a0: logique binaire. Cette \u00e9tape est r\u00e9p\u00e9t\u00e9e jusqu’\u00e0 ce que le mot soit trouv\u00e9 ou non (l’intersection des indices inf\u00e9rieur et sup\u00e9rieur de la plage se produit).<\/p>\n

Performances de cet algorithme – le meilleur des cas est lorsqu’un \u00e9l\u00e9ment est imm\u00e9diatement trouv\u00e9 au milieu du tableau O(1), le pire des cas d’\u00e9num\u00e9ration est O(log n)<\/p>\n

Pi\u00e8ges<\/h3>\n

Lors de l’impl\u00e9mentation de la recherche binaire, j’ai non seulement rencontr\u00e9 le probl\u00e8me int\u00e9ressant du manque de standardisation de la comparaison lexicographique<\/b> dans les biblioth\u00e8ques de langages de programmation, mais j’ai m\u00eame d\u00e9couvert l’absence d’un standard unifi\u00e9 pour l’impl\u00e9mentation localeCompare dans JavaScript<\/b>. La norme ECMAScript permet diff\u00e9rentes impl\u00e9mentations de cette fonction, c’est pourquoi lors du tri \u00e0 l’aide de localeCompare, des r\u00e9sultats compl\u00e8tement diff\u00e9rents peuvent \u00eatre observ\u00e9s sur diff\u00e9rents moteurs JavaScript.<\/p>\n

Par cons\u00e9quent, pour que l’algorithme fonctionne correctement, il faut trier et utiliser uniquement le m\u00eame<\/b> algorithme de comparaison lexicographique, sinon rien ne fonctionnera. Co-mais si, par exemple, vous essayez de trier un tableau dans Scala et d’effectuer une recherche \u00e0 l’aide de nodejs, sans impl\u00e9menter votre propre tri\/tri d’une impl\u00e9mentation, alors rien ne vous attend sauf une d\u00e9ception humaine.<\/p>\n

Sources<\/h3>\n

Qu’est-ce que la comparaison lexicographique et que repr\u00e9sente-t-elle ?<\/a>
\u041f\u043e\u0447\u0435\u043c\u0443 \u0434\u043b\u044f \u0432\u044b\u0447\u0438\u0441\u043b\u0435\u043d\u0438\u044f \u0441\u043b\u043e\u0436\u043d\u043e\u0441\u0442\u0438 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u043e\u0432 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u0442\u0441\u044f log N \u0432\u043c\u0435\u0441\u0442\u043e lb N?<\/a>
\n\u0414\u0432\u043e\u0438\u0447\u043d\u044b\u0439 \u043f\u043e\u0438\u0441\u043a<\/a>
\n\u0417\u043d\u0430\u0439 \u0441\u043b\u043e\u0436\u043d\u043e\u0441\u0442\u0438 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u043e\u0432<\/a>
\nhttps:\/\/stackoverflow.com\/questions\/52941016\/sorting-in-localecompare-in-javascript<\/a><\/p>\n

Code source<\/h3>\n

https:\/\/gitlab.com\/demensdeum\/algorithms<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"

Supposons que nous ayons besoin de savoir si l’adresse e-mail \u00ab\u00a0demensdeum@gmail.com\u00a0\u00bb est incluse dans la liste des adresses e-mail autoris\u00e9es pour la r\u00e9ception de lettres. . Parcourons toute la liste du premier au dernier \u00e9l\u00e9ment, en v\u00e9rifiant si l’\u00e9l\u00e9ment est \u00e9gal \u00e0 l’adresse sp\u00e9cifi\u00e9e – Impl\u00e9mentons un algorithme de recherche lin\u00e9aire. Mais cela prendra beaucoupContinue reading “Recherche binaire”<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_monsterinsights_skip_tracking":false,"_monsterinsights_sitenote_active":false,"_monsterinsights_sitenote_note":"","_monsterinsights_sitenote_category":0,"_jetpack_memberships_contains_paid_content":false,"footnotes":""},"categories":[61,52],"tags":[131,132],"class_list":["post-2374","post","type-post","status-publish","format-standard","hentry","category-techie","category-tutorials","tag-algorithms","tag-binary-search","entry"],"translation":{"provider":"WPGlobus","version":"3.0.2","language":"fr","enabled_languages":["en","ru","zh","de","fr","ja","pt","hi"],"languages":{"en":{"title":true,"content":true,"excerpt":false},"ru":{"title":true,"content":true,"excerpt":false},"zh":{"title":true,"content":true,"excerpt":false},"de":{"title":true,"content":true,"excerpt":false},"fr":{"title":true,"content":true,"excerpt":false},"ja":{"title":true,"content":true,"excerpt":false},"pt":{"title":true,"content":true,"excerpt":false},"hi":{"title":false,"content":false,"excerpt":false}}},"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/demensdeum.com\/blog\/fr\/wp-json\/wp\/v2\/posts\/2374","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/demensdeum.com\/blog\/fr\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/demensdeum.com\/blog\/fr\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/demensdeum.com\/blog\/fr\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/demensdeum.com\/blog\/fr\/wp-json\/wp\/v2\/comments?post=2374"}],"version-history":[{"count":19,"href":"https:\/\/demensdeum.com\/blog\/fr\/wp-json\/wp\/v2\/posts\/2374\/revisions"}],"predecessor-version":[{"id":3931,"href":"https:\/\/demensdeum.com\/blog\/fr\/wp-json\/wp\/v2\/posts\/2374\/revisions\/3931"}],"wp:attachment":[{"href":"https:\/\/demensdeum.com\/blog\/fr\/wp-json\/wp\/v2\/media?parent=2374"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/demensdeum.com\/blog\/fr\/wp-json\/wp\/v2\/categories?post=2374"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/demensdeum.com\/blog\/fr\/wp-json\/wp\/v2\/tags?post=2374"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}