Pesquisa Binária usando Bash-Shell
Publicado por Raimundo Alves Portela (última atualização em 20/07/2011)
[ Hits: 7.581 ]
Homepage: http://portelanet.com
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
#!/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"
Instalação automática do Nagios
Fluxbox: Wallpapers aleatórios
Converter Imagens e Documentos para PDF
Nenhum comentário foi encontrado.
Compartilhando a tela do Computador no Celular via Deskreen
Como Configurar um Túnel SSH Reverso para Acessar Sua Máquina Local a Partir de uma Máquina Remota
Configuração para desligamento automatizado de Computadores em um Ambiente Comercial
Como renomear arquivos de letras maiúsculas para minúsculas
Imprimindo no formato livreto no Linux
Vim - incrementando números em substituição
Efeito "livro" em arquivos PDF
Como resolver o erro no CUPS: Unable to get list of printer drivers
Não to conseguindo resolver este problemas ao instalar o playonelinux (1)
Excluir banco de dados no xampp (1)
[Python] Automação de scan de vulnerabilidades
[Python] Script para analise de superficie de ataque
[Shell Script] Novo script para redimensionar, rotacionar, converter e espelhar arquivos de imagem
[Shell Script] Iniciador de DOOM (DSDA-DOOM, Doom Retro ou Woof!)
[Shell Script] Script para adicionar bordas às imagens de uma pasta