Pesquisa Binária usando Bash-Shell [Shell Script]

Pesquisa Binária usando Bash-Shell

Publicado por Raimundo Alves Portela (última atualização em 20/07/2011)

[ Hits: 7.594 ]

Homepage: http://portelanet.com

Download pesquisaBinaria.sh

0 0

Denuncie Favoritos Indicar

Durante o tópico http://www.vivaolinux.com.br/topico/Off-Code-Cafe/Como-isso-e-possivel, acabei me relembrando de algumas aulas na Faculdade, onde aprendemos alguns métodos de pesquisa, que facilitam/agilizam a busca de informações, e eis que apresento a Pesquisa Binária.

"...A pesquisa ou busca binária (em inglês binary search algorithm ou binary chop) é um algoritmo de busca em vetores que requer acesso aleatório aos elementos do mesmo. Ela parte do pressuposto de que o vetor está ordenado e realiza sucessivas divisões do espaço de busca (divisão e conquista) comparando o elemento buscado (chave) com o elemento no meio do vetor. .."

Fonte: http://pt.wikipedia.org/wiki/Pesquisa_bin%C3%A1ria

Ok, basicamente meu script precisa de dois parâmetro, o primeiro é o valor a ser buscando, o segundo é um arquivo que contenha na primeira coluna, os valores da busca.

Exemplo de arquivo:
008912;RAIMUNDO
003145;PEDRO
001234;JOAO
001235;PAULO
003456;MARCIO
001315;BIANCA
000123;MARCELA
005670;BRUNO
009870;CAIO
098765;JUNIOR
100000;AMANDA
123456;PERCIVAL
111111;ASDADA
222111;ASDAS

Esconder código-fonte

#!/bin/bash
# Aplicando Método de Pesquisa Binária
# Por Raimundo A. Portela <rai3mb@gmail.com>

# Verifica os parâmetros
[ -z "$1" ] || [ -z "$2" ] && echo 'Sintaxe ./buscaBinaria.sh [valor_numerico] [arquivo]' && exit
# Verifica se o segundo parâmetro é um arquivo
! [ -f "$2" ] && echo 'Arquivo inexistente' && exit 

BUSCA=$1
ARQUIVO=$2

#Captura elementos
IDS=( ${array[@]} `cat "$ARQUIVO" | egrep '[^(^$)]' | cut -d';' -f 1 | sort`)

INICIO=1
FINAL=$(echo "${#IDS[@]}")
FINAL=$(($FINAL-1))

i=1
RESULTADO="O valor [$BUSCA] não foi encontrado no arquivo $ARQUIVO"
while [ $INICIO -le $FINAL ]
do
   MEIO=$((($INICIO+$FINAL)/2))
   if [ ${IDS[$MEIO]} -eq $BUSCA ]; then
      RESULTADO="O valor [$BUSCA] está no arquivo $ARQUIVO"
      break;
   elif [ $BUSCA -gt ${IDS[$MEIO]} ];then
      INICIO=$(($MEIO+1))
   else
      FINAL=$(($MEIO-1))
   fi
   i=$(($i+1))
done

echo "$RESULTADO"
echo
echo "Quantidade de Elementos na Busca: ${#IDS[@]}"
echo "Elemento que Buscamos: $BUSCA"
echo "Quantidade de Iterações: $i"

Scripts recomendados

Dicionário e tradutor baseado no Michaelis

SERVIDOR DHCP EM 5 MINUTOS

Atualização para KDE 3.5.2

Retra de iptables para DMZ na porta 80

Fazendo Failover entre 2 Links

Comentários

Nenhum comentário foi encontrado.