Pesquisa e Ordenação de Dados

Prévia do material em texto

<p>PESQUISA, ORDENAÇÃO E</p><p>TÉCNICAS DE</p><p>ARMAZENAMENTO</p><p>Atividade 1 Alisson Diel</p><p>30/09/2023</p><p>1 de 2</p><p>BUSCA SEQUENCIAL:</p><p>A busca sequencial é um método simples e direto de encontrar um elemento em uma lista de dados.</p><p>Funciona percorrendo cada elemento da lista, um por um, até encontrar o elemento desejado ou</p><p>atingir o final da lista.</p><p>Exemplo: Suponha que temos a seguinte lista de números: [12, 34, 56, 23, 45, 67, 89, 90]. Se</p><p>quisermos encontrar o número 45, começaríamos do início da lista e iríamos avançando até</p><p>encontrar o elemento desejado.</p><p>Pseudocódigo da Busca Sequencial:</p><p>função busca_sequencial(lista, alvo):</p><p>para cada elemento na lista:</p><p>se elemento == alvo:</p><p>retorne o índice do elemento</p><p>retorne -1 # Indica que o elemento não foi encontrado</p><p>BUSCA BINÁRIA:</p><p>A busca binária é uma técnica mais eficiente, mas requer que a lista esteja ordenada. Ela funciona</p><p>dividindo repetidamente a lista pela metade e comparando o elemento alvo com o elemento</p><p>central. Com base nessa comparação, a busca continua em uma das metades da lista até que o</p><p>elemento desejado seja encontrado.</p><p>Exemplo: Se temos a seguinte lista ordenada: [12, 23, 34, 45, 56, 67, 89, 90], e queremos encontrar o</p><p>número 45, começaríamos comparando-o com o elemento central, que é 45. Como é igual,</p><p>encontramos o elemento.</p><p>Pseudocódigo da Busca Binária:</p><p>função busca_binaria(lista, alvo):</p><p>esquerda = 0</p><p>direita = comprimento(lista) - 1</p><p>enquanto esquerda <= direita:</p><p>meio = (esquerda + direita) // 2</p><p>elemento_meio = lista[meio]</p><p>se elemento_meio == alvo:</p><p>retorne meio</p><p>se elemento_meio < alvo:</p><p>esquerda = meio + 1</p><p>senão:</p><p>direita = meio - 1</p><p>retorne -1 # Indica que o elemento não foi encontrado</p><p>PESQUISA, ORDENAÇÃO E</p><p>TÉCNICAS DE</p><p>ARMAZENAMENTO</p><p>Atividade 1 Alisson Diel</p><p>30/09/2023</p><p>2 de 2</p><p>DIFERENÇAS ENTRE BUSCA SEQUENCIAL E BUSCA BINÁRIA:</p><p>1. Complexidade Temporal:</p><p>• Busca Sequencial: O(n) - linear, onde 'n' é o número de elementos na lista.</p><p>• Busca Binária: O(log n) - logarítmica, mas requer uma lista ordenada.</p><p>2. Requisitos de Ordenação:</p><p>• Busca Sequencial: Não requer que a lista esteja ordenada.</p><p>• Busca Binária: A lista deve estar ordenada para funcionar corretamente.</p><p>3. Eficiência</p><p>• Busca Sequencial: É menos eficiente, especialmente em listas muito longas.</p><p>• Busca Binária: É mais eficiente, especialmente em listas longas, pois reduz o espaço de</p><p>busca pela metade a cada iteração.</p><p>Em resumo, a busca sequencial é simples e aplicável a qualquer lista, mas pode ser ineficiente para</p><p>listas muito grandes. A busca binária, por outro lado, é muito eficiente, mas exige que a lista esteja</p><p>ordenada. Portanto, a escolha entre os dois métodos dependerá do contexto em que são aplicados.</p>