Pesquisa Binária
breve introdução
Imagine que você entre no Facebook. Quando isso acontece, o Facebook precisa verificar se você tem uma conta no site, então ele procura seu nome no banco de dados. Supondo que seu nome seja "Kaká" (sim, esse mesmo que você está pensando), o Facebook poderia começar a procurar seu usuário pela letra "A". Mas você concorda que faz mais sentido começar pela metade, visto que o "K" não está no começo dessa lista.
Isto é um problema de busca. E, adiantando a sua resposta: sim! O algoritmo necessário para resolver esse problema é a pesquisa binária.
A pesquisa binária é um algoritmo que sua entrada deve ser uma lista ordenada de elementos. Se o elemento que você procura está na lista, a pesquisa retorna sua localização. Caso contrário, retorna None.
Exemplo
Estou pensando em um número entre 1 e 100
1, 2, 3, 4, 5, 6, 7, 8, 9, 10,
11, 12, 13, 14, 15, 16, 17, 18, 19, 20,
21, 22, 23, 24, 25, 26, 27, 28, 29, 30,
31, 32, 33, 34, 35, 36, 37, 38, 39, 40,
41, 42, 43, 44, 45, 46, 47, 48, 49, 50,
51, 52, 53, 54, 55, 56, 57, 58, 59, 60,
61, 62, 63, 64, 65, 66, 67, 68, 69, 70,
71, 72, 73, 74, 75, 76, 77, 78, 79, 80,
81, 82, 83, 84, 85, 86, 87, 88, 89, 90,
91, 92, 93, 94, 95, 96, 97, 98, 99, 100
Você deve tentar adivinhar o número que estou pensando com o menor número de tentativas possível. A cada tentativa, eu direi se você chutou muito para cima, muito para baixo ou acertou.
Digamos que você tenha começado tentando assim: 1, 2, 3, 4, 5... Veja como ficaria.
você:1, 2, 3, 4, 5
eu: Muito baixo
1, 2, 3, 4, 5, 6, 7, 8, 9, 10,
11, 12, 13, 14, 15, 16, 17, 18, 19, 20,
21, 22, 23, 24, 25, 26, 27, 28, 29, 30,
31, 32, 33, 34, 35, 36, 37, 38, 39, 40,
41, 42, 43, 44, 45, 46, 47, 48, 49, 50,
51, 52, 53, 54, 55, 56, 57, 58, 59, 60,
61, 62, 63, 64, 65, 66, 67, 68, 69, 70,
71, 72, 73, 74, 75, 76, 77, 78, 79, 80,
81, 82, 83, 84, 85, 86, 87, 88, 89, 90,
91, 92, 93, 94, 95, 96, 97, 98, 99, 100
Uma tentativa ruim de acertar o número
Isso se chama pesquisa simples. A cada tentativa, você está eliminando apenas UM ÚNICO número. Se o meu número fosse 99, você precisaria de 99 tentativas para acertar.
Uma maneira melhor de buscar seria começar com 50
você: 50
eu: Muito baixo
1, 2, 3, 4, 5, 6, 7, 8, 9, 10,
11, 12, 13, 14, 15, 16, 17, 18, 19, 20,
21, 22, 23, 24, 25, 26, 27, 28, 29, 30,
31, 32, 33, 34, 35, 36, 37, 38, 39, 40,
41, 42, 43, 44, 45, 46, 47, 48, 49, 50,
51, 52, 53, 54, 55, 56, 57, 58, 59, 60,
61, 62, 63, 64, 65, 66, 67, 68, 69, 70,
71, 72, 73, 74, 75, 76, 77, 78, 79, 80,
81, 82, 83, 84, 85, 86, 87, 88, 89, 90,
91, 92, 93, 94, 95, 96, 97, 98, 99, 100
Você eliminou metade dos números com apenas uma tentativa. Agora, você sabe que os números de 1 a 50 são muito baixos. Seguindo essa lógica, o próximo chute seria 75.
você: 75
eu: Muito alto
1, 2, 3, 4, 5, 6, 7, 8, 9, 10,
11, 12, 13, 14, 15, 16, 17, 18, 19, 20,
21, 22, 23, 24, 25, 26, 27, 28, 29, 30,
31, 32, 33, 34, 35, 36, 37, 38, 39, 40,
41, 42, 43, 44, 45, 46, 47, 48, 49, 50,
51, 52, 53, 54, 55, 56, 57, 58, 59, 60,
61, 62, 63, 64, 65, 66, 67, 68, 69, 70,
71, 72, 73, 74, 75, 76, 77, 78, 79, 80,
81, 82, 83, 84, 85, 86, 87, 88, 89, 90,
91, 92, 93, 94, 95, 96, 97, 98, 99, 100
Novamente, você pode cortar pela metade os números restantes. Em resumo, com a pesquisa binária, você chuta um número intermediário e elimina a metade dos números restantes a cada vez.
Se fôssemos continuar com esse jogo de adivinhação, aqui está a quantidade de números que você pode eliminar a cada tentativa.
100 -> 50 -> 25 -> 13 -> 7 -> 4 -> 2 -> 1
Seja qual for o número que você esteja pensando de 1 a 100, conseguimos adivinhá-lo com no máximo sete tentativas.
Outro exemplo
Suponha que você esteja procurando uma palavra em um dicionário de 240.000 palavras. Na pior das hipóteses, quantas etapas você precisaria para acertar?
na pesquisa simples, na pior das hipóteses precisaríamos de 240 mil tentativas, já na pesquisa binária 18 tentativas.
240.000 palavras
120.000 palavras
60.000 palavras
30.000 palavras
15.000 palavras
7.500 palavras
3.750 palavras
1.875 palavras
937 palavras
468 palavras
234 palavras
117 palavras
58 palavras
29 palavras
14 palavras
7 palavras
3 palavras
2 palavras
1 palavra
de maneira geral, para uma pesquisa de n números a pesquisa binária precisa de \log _2\left(n\right) enquanto a pesquisa simples precisa de n etapas.
tempo de execução
notação Big O
A notação Big O é uma notação especial que indica a eficiência de um algoritmo. O tempo de execução na notação Big O é O(n)
A notação Big O não mede o tempo diretamente, mas sim a quantidade de operações, ou seja, como o número de operações cresce conforme o tempo aumenta.
A notação Big O permite que você compreenda o número de operações necessárias para executar um algoritmo conforme o tamanho do tempo aumenta.
A pesquisa binária precisa de \log _{\:}\left(n\right) operações para verificar uma lista de tamanho n então sua notação seria
O(\log _{\:}\left(n\right)).
a notação big O fornece o tempo de execução na pior das hipóteses
não conseguir colocar as imagens que fiz no canva, se alguém souber pfvr me ajude kkkkkkkkkk
tomei como referência o livro: Entendendo Algoritmos: Um Guia Ilustrado Para Programadores e Outros Curiosos. o link para comprar o livro vai está na Fonte