Pesquisa Binária usando Bash-Shell
Publicado por Raimundo Alves Portela (última atualização em 20/07/2011)
[ Hits: 7.762 ]
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"
Dell 1390 WLAN (Broadcom 4311)
Filtrando trabalhos de impressão...
Pra quem não usa WhatsUp e Nagios mas tem um *inx.
Converter Wav para MP3 usando Lame e PPSS para multi processamento via shell script - Asterisk
Nenhum coment�rio foi encontrado.
Comparação entre os escalonadores BFQ e MQ-Deadline (acesso a disco) no Arch e Debian
Conciliando o uso da ZRAM e SWAP em disco na sua máquina
Servidor de Backup com Ubuntu Server 24.04 LTS, RAID e Duplicati (Dell PowerEdge T420)
Visualizar câmeras IP ONVIF no Linux sem necessidade de instalar aplicativos
Converter os repositórios Debian para o novo formato com as chaves
Instalando Spotify no Debian 13
Realizar overclock no Miyoo Mini (plus ou normal)
Erro na inicialização do Debian como resolver (0)
linux mint reconhece microfone de lapela como fone de ouvido sem micro... (3)
Como desinstalar o GIMP? [RESOLVIDO] (1)