{"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\/pt\/2019\/12\/08\/binary-search\/","title":{"rendered":"Pesquisa bin\u00e1ria"},"content":{"rendered":"

Suponha que precisamos descobrir se o endere\u00e7o de e-mail \u201cdemensdeum@gmail.com<\/a>\u201d est\u00e1 inclu\u00eddo na lista de endere\u00e7os de e-mail permitidos para recebimento de cartas .<\/p>\n

Vamos percorrer toda a lista do primeiro ao \u00faltimo elemento, verificando se o elemento \u00e9 igual ao endere\u00e7o especificado – Vamos implementar um algoritmo de busca linear. Mas isso vai demorar muito ou n\u00e3o?<\/p>\n

Para responder a esta pergunta, use a nota\u00e7\u00e3o \u201cComplexidade de tempo dos algoritmos\u201d, \u201cO\u201d. O tempo de opera\u00e7\u00e3o da busca linear no pior caso \u00e9 igual ao en\u00e9simo n\u00famero de elementos do array, vamos escrever isso na nota\u00e7\u00e3o \u201cO\u201d – Sobre). A seguir, precisamos explicar que para qualquer algoritmo conhecido existem tr\u00eas indicadores de desempenho – tempos de execu\u00e7\u00e3o do melhor caso, do pior caso e do caso m\u00e9dio. Por exemplo, o endere\u00e7o de e-mail \u201cdemensdeum@gmail.com<\/a>\u201d est\u00e1 no primeiro \u00edndice do array, ent\u00e3o ele ser\u00e1 encontrado na primeira etapa do do algoritmo, segue-se que o tempo de execu\u00e7\u00e3o \u00e9, na melhor das hip\u00f3teses, – O(1); e se estiver no final da lista, ent\u00e3o este \u00e9 o pior caso – Sobre(n)<\/p>\n

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

Mas e os detalhes de implementa\u00e7\u00e3o de software e desempenho de hardware, eles devem influenciar o grande O? Agora respire fundo e imagine que o c\u00e1lculo da complexidade do tempo \u00e9 calculado para alguma m\u00e1quina abstrata ideal, na qual existe apenas esse algoritmo e nada mais.<\/p>\n

Algoritmo<\/h3>\n

Ok, acontece que a pesquisa linear \u00e9 bastante lenta, vamos tentar usar a pesquisa bin\u00e1ria. Para come\u00e7ar, deve-se esclarecer que n\u00e3o trabalharemos com dados bin\u00e1rios; este nome foi dado a este m\u00e9todo devido \u00e0s peculiaridades de seu trabalho. Inicialmente classificamos o array em ordem lexicogr\u00e1fica<\/a>, ent\u00e3o o algoritmo pega o intervalo de todo o array, obt\u00e9m o elemento do meio do intervalo, compara-o lexicograficamente<\/a>, e dependendo do resultado da compara\u00e7\u00e3o, decide qual intervalo usar para pesquisas adicionais – a metade superior da corrente ou a parte inferior. Ou seja, a cada etapa da pesquisa \u00e9 tomada uma decis\u00e3o a partir de dois – l\u00f3gica bin\u00e1ria. Esta etapa \u00e9 repetida at\u00e9 que a palavra seja encontrada ou n\u00e3o seja encontrada (ocorre a intersec\u00e7\u00e3o dos \u00edndices inferior e superior do intervalo).<\/p>\n

Desempenho deste algoritmo – o melhor caso \u00e9 quando um elemento \u00e9 imediatamente encontrado no meio do array O(1), o pior caso de enumera\u00e7\u00e3o \u00e9 O(log n)<\/p>\n

Armadilhas<\/h3>\n

Ao implementar a pesquisa bin\u00e1ria, n\u00e3o apenas encontrei o interessante problema da falta de padroniza\u00e7\u00e3o da compara\u00e7\u00e3o lexicogr\u00e1fica<\/b> em bibliotecas de linguagens de programa\u00e7\u00e3o, mas tamb\u00e9m descobri a aus\u00eancia de um padr\u00e3o unificado para implementa\u00e7\u00e3o localeCompare em JavaScript<\/b>. O padr\u00e3o ECMAScript permite diferentes implementa\u00e7\u00f5es desta fun\u00e7\u00e3o, e \u00e9 por isso que ao classificar usando localeCompare, resultados completamente diferentes podem ser observados em diferentes motores JavaScript.<\/p>\n

Portanto, para que o algoritmo funcione corretamente, \u00e9 necess\u00e1rio classificar e usar apenas o mesmo<\/b> algoritmo de compara\u00e7\u00e3o lexicogr\u00e1fica, caso contr\u00e1rio nada funcionar\u00e1. Co-mas se, por exemplo, voc\u00ea tentar classificar um array no Scala e pesquisar usando nodejs, sem implementar sua pr\u00f3pria classifica\u00e7\u00e3o\/classifica\u00e7\u00e3o de uma implementa\u00e7\u00e3o, nada o aguardar\u00e1, exceto decep\u00e7\u00e3o com a humanidade.<\/p>\n

Fontes<\/h3>\n

O que \u00e9 compara\u00e7\u00e3o lexicogr\u00e1fica e o que ela representa?<\/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

C\u00f3digo fonte<\/h3>\n

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

Suponha que precisamos descobrir se o endere\u00e7o de e-mail \u201cdemensdeum@gmail.com\u201d est\u00e1 inclu\u00eddo na lista de endere\u00e7os de e-mail permitidos para recebimento de cartas . Vamos percorrer toda a lista do primeiro ao \u00faltimo elemento, verificando se o elemento \u00e9 igual ao endere\u00e7o especificado – Vamos implementar um algoritmo de busca linear. Mas isso vai demorarContinue reading “Pesquisa bin\u00e1ria”<\/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":"pt","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\/pt\/wp-json\/wp\/v2\/posts\/2374","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/demensdeum.com\/blog\/pt\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/demensdeum.com\/blog\/pt\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/demensdeum.com\/blog\/pt\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/demensdeum.com\/blog\/pt\/wp-json\/wp\/v2\/comments?post=2374"}],"version-history":[{"count":19,"href":"https:\/\/demensdeum.com\/blog\/pt\/wp-json\/wp\/v2\/posts\/2374\/revisions"}],"predecessor-version":[{"id":3931,"href":"https:\/\/demensdeum.com\/blog\/pt\/wp-json\/wp\/v2\/posts\/2374\/revisions\/3931"}],"wp:attachment":[{"href":"https:\/\/demensdeum.com\/blog\/pt\/wp-json\/wp\/v2\/media?parent=2374"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/demensdeum.com\/blog\/pt\/wp-json\/wp\/v2\/categories?post=2374"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/demensdeum.com\/blog\/pt\/wp-json\/wp\/v2\/tags?post=2374"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}