Sentinel linear search

SENTINEL LINEAR SEARCH

ALEX ONEDA, LAYNE FIRMINO, GUSTAVO PEROTTO,GUILHERME SCHWEITZER E RAFAELA CORREA

INTRODUÇÃO

SENTINEL LINEAR SEARCH

O Sentinel Linear Search é uma variante do Linear Search que usa um valor sentinela para otimizar o processo de busca. Ele tem como base a idéia da Linear Search, porém reduzindo o número de comparações necessárias para encontrar um elemento da lista. Nesse método, substituímos o último elemento da lista com o próprio elemento da busca e rodamos um loop while para verificar se existe alguma cópia do elemento da busca na lista, e assim que encontrado, paramos e saímos do loop.

EFICIÊNCIA

COMPLEXIDADE

CENÁRIOS DE USO

O Sentinel Linear Search pode ter uma vantagem em termos de eficiência quando comparada à Linear Search normal, especialmente em grandes listas. A adição do elemento sentinela permite que o algoritmo evite verificar a condição de parada a cada iteração, tornando-se um pouco mais eficiente.

Em média, o Sentinel Linear Search percorre metade do conjunto de dados antes de encontrar o elemento pesquisado ou chegar ao final. Esse método não requer espaço adicional significativo, já que utiliza apenas variáveis adicionais para armazenar o elemento sentinela para ser pesquisado e usado como parada.

O Sentinel Linear Search é ideal onde os cenários são, por exemplo, conjuntos de dados não ordenados onde a posição do elemento desejado é desconhecida. É apropriado também em situações com baixo custo de pré-processamento, devido a adição do elemento sentinela. Sua abordagem linear se mostra vantajosa em cenários onde uma inicialização rápida é crucial.

using System; class Program { static void sentinelSearch(int[] lista, int tamanho, int valor) { int ultimo = lista[tamanho - 1]; lista[tamanho - 1] = valor; int i = 0; while (lista[i] != valor) i++; lista[tamanho - 1] = ultimo; if ((i < tamanho - 1) || (lista[tamanho - 1] == valor)) { Console.WriteLine($"O valor [{valor}] foi encontrado no índice [{i}]"); } else Console.WriteLine("Valor não encontrado"); } public static void Main() { int[] lista = { 10, 20, 180, 30, 60, 50, 110, 100, 70 }; sentinelSearch(lista, lista.Length, 70); } }

Salvamos o último valor original da lista na variável “ultimo”

Definimos o último elemento da lista para o valor procurado. (Esse é o valor sentinela);

Definimos a variável do índice (i) como o zero, para começarmos o loop no primeiro elemento da lista;

Usamos um loop while para iterar a lista, comparando cada elemento com o valor pesquisado (para automático já que o último item atual é o valor sentinela, para evitar buscas fora do limite da lista);

Se o elemento atual é igual o valor pesquisado, retornamos o índice do elemento atual.

Incrementamos a variável do índice (i) em +1 a cada iteração do loop.

Retornamos o item do último índice da variável “ultimo” para o seu local original.

Após completo o loop, checamos com um “if” se o valor da variável do índice é menor que o tamanho total -1 da lista ou se o item do último índice (agora o valor original já que substituído no passo anterior) é igual ao valor pesquisado.