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.579 ]

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

duplex_record: mixando áudio do microfone e saída de áudio de um programa via P

Unificando arquivos de bloqueio e liberação no squid

Script para criação de usuarios.

Ver último twitter pelo terminal ou na barra de notificação

Configurando um Domínio no BIND9 com Debian 3.1

Comentários

Nenhum comentário foi encontrado.