LogRitmo navegador / ativofase / 02LR / fase 02 · ativaCorte o espaço de busca pela metade a cada decisão.
pré-condição / entrada ordenada
A busca binária só é válida quando os valores estão em ordem. A bancada ordena a sequência antes do playback para tornar essa condição visível.
Execuções concluídas nesta bancada, medidas durante o playback ativo no navegador e salvas apenas neste dispositivo.
Execute o algoritmo até o fim para transformar esta bancada em uma série de medições reais.
Use quando os dados estão ordenados e você precisa de uma resposta rápida em coleções maiores.
mude o meio
A cada decisão, metade dos candidatos deixa de existir.
Exige uma sequência ordenada antes de começar.
A cada decisão, o algoritmo elimina metade dos candidatos. O log₂(n) conta quantos cortes pela metade são necessários para chegar a um item.
Com 16 itens são, no máximo, 4 cortes; com 32, 5. Dobrar a entrada adiciona apenas um corte.Escolha duas técnicas diferentes. As curvas usam a mesma escala visual para explicar como o custo tende a aumentar.
Use este par para observar por que O(n²) acumula trabalho mais depressa que O(n log n) quando a lista cresce. Merge Sort tende a crescer mais devagar do que Bubble Sort quando aumentam quantidade de itens (n). Isso descreve tendência assintótica, não mede o tempo do seu aparelho.
Binary Search não “adivinha” onde a chave está. Ela preserva um intervalo candidato e compara o alvo com o seu meio. Em uma sequência crescente, um valor menor que o alvo torna toda a metade esquerda incompatível; um valor maior torna a metade direita incompatível. Essa conclusão depende da mesma ordem usada para organizar e comparar os dados.
A faixa pesquisada precisa estar ordenada segundo o mesmo critério da consulta. A bancada ordena a sequência para tornar essa pré-condição visível; em um sistema real, decidir ou manter essa ordem faz parte do problema, não é uma etapa gratuita.
Antes de cada comparação, pelo menos uma ocorrência possível está entre low e high. Se o meio é menor, low = mid + 1; se é maior, high = mid - 1. O meio incompatível também sai do intervalo.
Cada passo sem igualdade remove ao menos uma posição candidata. Encontrar o meio encerra com uma ocorrência; quando low > high, nenhum índice compatível restou e a ausência está comprovada.
O(log n) conta cortes; não promete tempo idêntico em qualquer coleção.Após cada comparação, restam aproximadamente metade dos candidatos. Em um array, acessar o meio é direto, por isso a busca iterativa usa memória auxiliar O(1). Em uma lista ligada, chegar repetidamente ao meio pode exigir travessias longas: as comparações continuam poucas, mas o custo de acesso deixa de acompanhar a mesma leitura simples.
O contrato básico retorna uma ocorrência ao encontrar igualdade; com duplicatas, ela pode não ser a primeira. Para paginação, faixas, inserção ordenada ou qualquer regra que dependa de fronteira, escolha explicitamente a variante desejada em vez de depender por acaso do índice retornado.
Para uma única consulta em uma lista pequena e fora de ordem, Linear Search evita a preparação de ordenar. Para muitas consultas sobre dados estáticos e já ordenados, Binary Search reduz as comparações por consulta. Em termos simplificados, compare q·n de varreduras lineares com n log n + q log n de ordenar uma vez e buscar q vezes. O modelo não substitui avaliar atualizações, memória e a estrutura de dados, mas impede que O(log n) vire uma recomendação automática.
Cada linha acompanha o gesto visual. Troque de linguagem e continue no mesmo passo.
function binarySearch(items, target) { // Halve the sorted search intervallet low = 0, high = items.length - 1;while (low <= high) {const mid = Math.floor((low + high) / 2);if (items[mid] === target) return mid;if (items[mid] < target) low = mid + 1;else high = mid - 1;}return -1;}