Algoritmos: Busca Linear e Busca Binária

cin — Thu, 05 Dec 2024 13:56:24 +0000

Há alguns algoritmos simples que introduzem conceitos básicos de lógica e estrutura de dados, enquanto outros visam maior complexidade.

Algoritmos de busca são úteis para localizar informações em volumes de dados, como encontrar um contato em uma lista telefônica ou um arquivo em um computador.

Nesse sentido, o presente artigo visa apresentar uma introdução aos conceitos que envolvem algoritmos de Busca Linear e Busca Binária.

1. Linear Search

Percorre uma lista sequencialmente para encontrar um elemento
Como exemplar seria buscar um número específico em um array

O Algoritmo de Linear Search, em declaração narrativa, significa ter um array de números inteiros e um valor que será a referência para a busca, denominado de target, os quais serão os parâmetros de entrada. Nesse sentido, tem-se uma função que recebe esses valores, e com isso, primeiro percorre-se cada posição desse array até o tamanho máximo de posições existentes, utilizando primariamente um for para isso, e então, com um if, condiciona-se a verificação para: se cada posição possui o valor igual ao target. Caso o valor seja encontrado, a função retorna o índice dessa posição, ou retorna o -1, representando os casos não encontrados.

Um exemplo utilizando o JavaScript, seria:

function linearSearch(array, target) {
  for (let i = 0; i < array.length; i++) {
    if (array[i] === target) {
      return i; 
    }
  }
  return -1; 
}

Portanto, esse algoritmo visa retornar a posição, ou índice, onde o elemento se encontra, ou ainda, ele simplesmente localiza o primeiro elemento correspondente, sem necessidade de continuar após encontrá-lo. Esse comportamento ocorre devido às instruções do algoritmo, o qual, ao possuir sua condição satisfeita, executa o return com o índice do elemento, e após isso sai do loop, finalizando a função.

Este algoritmo pode ser útil em cenários onde há pequenas listas ou não ordenadas. Cada elemento pode precisar ser percorrido, e não há o uso de memória extra.

2. Binary Search

Percorre uma lista ordenada para encontrar um elemento
Como exemplo seria buscar um número específico em um array

O Algoritmo de Binary Search é uma forma mais eficiente de algoritmo para encontrar um valor determinado em um array ordenado. Este funciona dividindo repetidamente o range de busca na metade, o que faz com que ele seja significantemente mais rápido do que a busca linear para grandes datasets. A busca binária tem complexidade O(log n), enquanto a busca linear é O(n).

Como exemplo em JavaScript, tem-se:

function binarySearch(array, target) {
  let low = 0;
  let high = array.length - 1;

  while (low <= high) {
    const middle = Math.floor((low + high) / 2);

    if (array[middle] < target) {
      low = middle + 1;
    } else if (array[middle] > target) {
      high = middle - 1;
    } else {
      return middle;
    }
  }
  return -1;
}

A lógica consiste em iniciar com dois ponteiros, um no início (low) e outro no final (high) do array. Assim, calcula-se o index do meio const middle = Math.floor((low + high) / 2). Com isso, compara-se o elemento do meio com o target em cada etapa: se o elemento do meio igualar ao target, retorna-se o index. Porém se o elemento do meio for menor do que o target, ou middle < target, implica em descartar os menores números, colocando o início como low = middle + 1. Se o elemento do meio, por sua vez, for maior que o target middle > target, descarta-se os números maiores que o target, ajustando o índice final para high = middle - 1. Esse processo se repete até que o target seja encontrado ou quando o range se tornar inválido, no caso low > high.

A busca binária pode ser eficiente ao encontrar dados ordenados, como em um dicionário alfabético ou em um conjunto de datas ordenadas. Tendem a ser mais rápidos e eficientes, pois pode-se dividir o problema em subproblemas menores em cada iteração.

Portanto, entende-se, assim, que a busca linear é simples e funciona em pequenas listas. Já a busca binária é muito mais eficiente, mas exige dados ordenados.

Entender como diferentes algoritmos funcionam e seus contextos de uso é um passo importante para a construção de soluções computacionais eficientes. Experimente implementar e analisar esses métodos, e descubra como essas estratégias podem ser adaptadas para resolver desafios do mundo real. =)

DEV Community: cin

Algoritmos: Busca Linear e Busca Binária