Programação de Computadores

Comparando Algoritmos e Busca

em Arranjos

Alan
de
Freitas
 Algoritmos
• Um algoritmo é um procedimento de
passos para cálculos.
• Este procedimento é composto de
instruções que definem uma função
• Até o momento, vimos apenas códigos em
C++ para descrever ideias
• Já um algoritmo pode descrever ideias
para pessoas que programem em outras
linguagens de programação
 Exemplo
Código em C++ Algoritmo
int max(int[] a, int n){ Entrada: Conjunto de números inteiros A
int i, temp; Saída: Maior elemento deste conjunto
temp = a[0];
for (i = 1; i < n; i++){ m ← primeiro elemento de A
if (temp < a[i]){ Para todos os outros elementos Ai de A
temp = a[i];
}
se o elemento Ai for maior que m
} m ← Ai
return temp; retorne o valor de m
}
 Definição
• Apesar de ser um conjunto de regras que define uma
sequência, não existe uma definição formal e geral de
algoritmo.
• Podem ser incluídos algoritmos que não fazem cálculos?
• O algoritmo precisa sempre parar?
• Um programa que não para é um algoritmo?
• Podem ser incluídos programas que só param com
intervenção do usuário?
• Programas que dependem do usuário são algoritmos?
• Algoritmos podem ter componentes aleatórios?
Expressando algoritmos
• Há também várias maneiras de se
expressar um algoritmo:
• Linguagem natural (Português)
• Pseudo-código (Listagem das operações
matemáticas)
• Diagramas (Quadrados e setas)
• As próprias linguagens de programação
 Algoritmos
• Estamos mesmo assim interessados em
estudar algoritmos em vez de códigos em
linguagens de programação
• Isso porque queremos conclusões amplas
sobre a análises que fazemos dos
algoritmos
• Em programação, esta análise mais ampla
permite ajudar pessoas que utilizam
diferentes linguagens
Modelos de comparação
• Nem sempre 2 algoritmos que resolvem o
mesmo problema são igualmente
eficientes…
• Como comparar algoritmos?
• Alguns são mais rápidos…
• Outros gastam menos memória…
• Outros obtém soluções de melhor
qualidade…
Medida de custo real
• Usualmente inadequada
• Depende muito do sistema em geral
• Hardware, compilador, quantidade
disponível de memória
• Pode ser vantajosa quando dois
algoritmos têm comportamento similar
• Os custos reais de operação são então
considerados
Medida por Modelos Matemáticos
• Especificamos um conjunto de operações
e seus custos
• Usualmente, apenas as operações mais
importantes do algoritmo são
consideradas
• Comparações
• Atribuições
• Chamadas de função
Complexidade de Algoritmos
• Para se medir o custo de um algoritmo,
definimos uma função de custo ou função de
complexidade f
• f(n) pode medir o tempo necessário para
executar um algoritmo
• f(n) pode medir o tempo determinando quantas
vezes uma operação relevante será executada
• f(n) pode medir a memória gasta para executar
um algoritmo
Considere o algoritmo abaixo…

int max(int a[], int n){

int i, temp;
temp = a[0];
for (i = 1; i < n; i++){
if (temp < a[i]){
temp = a[i];
}
}
return temp;
}
 int max(int a[], int n){
int i, temp;
temp = a[0];
for (i = 1; i < n; i++){
if (temp < a[i]){
temp = a[i];
}
}
return temp;
}

Ele retorna o maior elemento de um arranjo a

com n elementos.
Para achar o menor elemento, ele guarda o
valor do primeiro elemento do arranjo…

int max(int a[], int n){

int i, temp;
temp = a[0];
for (i = 1; i < n; i++){
if (temp < a[i]){
temp = a[i];
}
}
return temp;
}
Para achar o menor elemento, ele guarda o
valor do primeiro elemento do arranjo…

int max(int a[], int n){

int i, temp;
temp = a[0];
for (i = 1; i < n; i++){
if (temp < a[i]){
temp = a[i];
}
}
return temp;
}

…e o compara com todos os outros elementos

do arranjo
Para um arranjo de n elementos e uma função f(n) do
número de comparações temos que o custo do
algoritmo é:
int max(int a[], int n){
int i, temp;
temp = a[0];
for (i = 1; i < n; i++){
if (temp < a[i]){
temp = a[i];
}
}
return temp;
}

f(n) = n - 1
 Note que a operação relevante deste algoritmo é o
número de comparações.

int max(int a[], int n){

int i, temp;
temp = a[0];
for (i = 1; i < n; i++){
if (temp < a[i]){
temp = a[i];
}
}
return temp;
}

No caso geral, não é interessante medir o número de

operações de atribuição pois elas só acorrem quando
a comparação retorna true
Melhor caso, pior caso e caso médio
int max(int a[], int n){
int i, temp;
temp = a[0];
for (i = 1; i < n; i++){
if (temp < a[i]){
temp = a[i];
}
}
return temp;
}

Suponha agora um computador no qual as operações

de atribuição são muito custosas.

Estamos então interessados no número de operações

de atribuição como medida de tempo.
Melhor caso, pior caso e caso médio
int max(int a[], int n){
int i, temp;
temp = a[0];
for (i = 1; i < n; i++){
if (temp < a[i]){
temp = a[i];
false
}
}
return temp;
}

O melhor caso em relação a tempo é quando a

comparação é sempre false pois temos apenas uma
operação de atribuição.

Isso ocorre quando o primeiro elemento já é o maior.

Melhor caso, pior caso e caso médio
int max(int a[], int n){
int i, temp;
temp = a[0];
for (i = 1; i < n; i++){
if (temp < a[i]){
temp = a[i];
false
}
}
return temp;
}

Neste melhor caso, podemos dizer que

f(n) = 1
pois sempre teremos apenas uma operação de
atribuição
Melhor caso, pior caso e caso médio
int max(int a[], int n){
int i, temp;
temp = a[0];
for (i = 1; i < n; i++){
if (temp < a[i]){
temp = a[i];
true
}
}
return temp;
}

Na situação contrária, se a comparação é sempre

verdadeira, temos nosso pior caso em relação ao
número de atribuições.

Isso ocorre quando os elementos do arranjo estão em

ordem crescente.
Melhor caso, pior caso e caso médio

int max(int a[], int n){

int i, temp;
temp = a[0];
for (i = 1; i < n; i++){
if (temp < a[i]){
temp = a[i];
true
}
}
return temp;
}

Neste pior caso, podemos dizer que temos que

f(n) = n
pois sempre teremos uma operação de atribuição para
cada elemento do arranjo
Melhor caso, pior caso e caso médio

int max(int a[], int n){

int i, temp;
temp = a[0];
for (i = 1; i < n; i++){
if (temp < a[i]){
temp = a[i];
true / false
}
}
return temp;
}

Já o caso médio, ou caso esperado, é a média de

todos os casos possíveis. O caso médio é muito mais
difícil de ser obtido pois depende da nossa estimativa
de probabilidades de cada entrada.
Melhor caso, pior caso e caso médio

int max(int a[], int n){

int i, temp;
temp = a[0];
for (i = 1; i < n; i++){
if (temp < a[i]){
temp = a[i];
true / false
}
}
return temp;
}

Se supormos que a probabilidade de um comparação

ser true é de 50%, podemos dizer que o caso médio é
f(n) = 1 + (n-1)/2
Porém, esta é uma suposição pouco provável na
prática.
 Notação O

• A notação O é utilizada para descrever

a tendência de uma função
• Ela é muito utilizada em computação
para classificar algoritmos de acordo
com a taxa de crescimento de suas
funções
 • A análise de um algoritmo geralmente conta com apena
elementares
Dominação Assintótica
• A medida de custo ou medida de complexidade relata o
tico da operação considerada
• Uma função f(n) • Ou seja, para números
• Definição:
domina Uma função fgrandes
(n) domina
cf(n) assintoticamen
será
se existem duas constantes
assintoticamente positivas
sempre maiorc eque tais que,
m g(n),
|g(n)|  c ⇥ |f
outra função (n)|
g(n) se para alguma constante c
existem duas
constantes positivas
c e m tais que, para
n ≥ m, temos
|g(n)| ≤ c × |f(n)|

DCOMP/UFSJ AEDSII Intr. An. Complex.

Notação O para dominação
• Quando uma função g(n) = O(f(n)),
dizemos que:
• g(n) é O de f(n)
• f(n) domina g(n) assintoticamente
• A notação é importante para comparar
algoritmos pois não estamos
interessados em funções exatas de custo
mas sim do comportamento da função
 Exemplo 1
• Dadas as funções
• g(n) = (n+1)2
• f(n) = n2
• As duas funções se dominam
assintoticamente pois:
• g(n) = O(f(n)) pois g(n) ≤ 4f(n) para n>1
• f(n) = O(g(n)) pois f(n) ≤ g(n)
 Exemplo 2
• Dadas as funções
2
• g(n) = (n+1)
3
• f(n) = n
• A segunda função domina a primeira
• g(n) = O(f(n)) pois g(n) ≤ cf(n) para um c
coerente e a partir de n > 1
• Porém a primeira não domina a segunda:
• Pois f(n) ≤ cg(n) seria uma afirmação falsa para
qualquer c e a partir de qualquer n
 Limites fortes
• g(n) = 3n3+2n2+n é O(n3)
• Pois g(n) ≤ 6n3, para n ≥ 0
• É claro que também podemos dizer que
g(n) = O(n4), porém esta seria uma
afirmação fraca
• Para analisar comportamentos de
algoritmos, estamos interessados em
afirmações fortes
Operações com notação O
Operações com a notação O

DCOMP/UFSJ AEDSII
· Intr. An. Complex. 35
Operações com notação O
Uma função sempre se domina pois basta a
multiplicar por uma constante para que seja maior
Operações com a notação O
que ela mesmo.
Operações com notação O
O mesmo vale para esta função O(f(n)) multiplicada
por uma constante, pois basta multiplicarmos f(n) por
Operações com a notação O
uma constante ainda maior para que seja dominada.
Operações com notação O
A soma de duas funções dominadas por f(n) é ainda
dominada por f(n) pois esta diferença ainda pode ser
Operações com a notação O
compensada por uma constante.
Operações com notação O
Se uma função é dominada por uma função dominada
por f(n), a primeira função é também dominada por
Operações com a notação O
f(n)
Operações com notação O
A soma de duas funções será dominada pela maior
função que
Operações comas domina.
a notação O
Operações com notação O
A multiplicação de duas funções será dominada pela
multiplicaçãoOperações
das funções que asOdominavam.
com a notação
Classes de algoritmos

• Com as funções de complexidade de

cada programa, podemos compará-los
• No caso geral, para valores grandes
de n, um programa que leva tempo
O(n) é melhor que um programa que
leva tempo O(n2)
 f(n) = O(1)
• Dizemos que algoritmos O(1) têm
complexidade constante
• Eles têm o mesmo desempenho
independente do valor de n
• Estes são os algoritmos onde as
instruções são executadas um número
fixo de vezes
 f(n) = O(log n)
• Dizemos que algoritmos O(log n) têm
complexidade logarítmica
• Algoritmos típicos desta classe são os
que dividem problemas em outros
menores na forma de divisão e
conquista
• São ainda muito rápidos, já que se n =
1000000, log10n = 6
 f(n) = O(n)
• Dizemos que algoritmos O(n) têm
complexidade linear
• Neste algoritmos, se dobramos n, o
tempo de resposta dobra
• Algoritmos típicos desta classe são os
que realizam um pequeno trabalho
sobre cada um dos n elementos de
entrada
 f(n) = O(n log n)
• Algoritmos típicos desta classe são os que
quebram o problema em problemas menores,
fazem uma operação em cada um dos
elementos e depois combinam as soluções
• Se n é 1 milhão, n log2n é cerca de 20 milhões
• Se n é 10 milhões, n log2n é cerca de 42
milhões
• Ou seja, f(n) é pouco mais que o dobro ao
dobrar o tamanho de n
 f(n) = O(n ) 2

• Dizemos que algoritmos O(n2) têm

complexidade quadrática
• Neste algoritmos, se dobramos n, o
tempo de resposta se multiplica por 4
• São úteis para problemas
relativamente pequenos
• Algoritmos típicos desta classe são os
que processam n elementos par-a-par
 f(n) = O(n ) 3

• Dizemos que algoritmos O(n3) têm

complexidade cúbica
• Neste algoritmos, se dobramos n, o
tempo de resposta se multiplica por 8
• São úteis apenas para problemas
muito pequenos
 f(n) = O(2 ) n

n
• Dizemos que algoritmos O(2 ) têm complexidade
exponencial
• Quando n = 20, o tempo de execução já é cerca de 1
milhão
• Não são algoritmos muito úteis na prática
• Algoritmos típicos desta classe são os que usam
força-bruta para resolver problemas que envolvam
combinações
• São testadas todas as soluções possíveis até que
se encontre a certa
 f(n) = O(n!)
• Dizemos que algoritmos O(n!) também têm
complexidade exponencial, apesar de serem
muito piores que O(2n)
• Não são úteis na prática
• Algoritmos típicos desta classe são os que
usam força-bruta para resolver problemas
que envolvam permutações
• O computador levaria séculos para
resolver problemas pequenos
 Busca em Arranjos
• Como sabemos, arranjos são uma
maneira de se armazenar muita
informação em série
• Esta informação, em situações práticas,
é usualmente dividida em registros do
C++ com o recurso struct
• Precisamos de estratégias para
encontrar dados nestes arranjos
 Busca em arranjos
• Usualmente, cada struct do arranjo
tem um campo que chamamos de chave
• Por exemplo, suponha um arranjo de
dados do tipo Aluno:

struct Aluno{
string nome;
double nota_prova1;
double nota_prova2;
int matricula;
}
 Busca em arranjos
• Nesta estrutura, cada aluno terá um nome,
uma nota para cada prova e um número de
matrícula.
• Como os números de matrícula não se
repetem, eles são bons candidatos a serem o
membro chave dos alunos
struct Aluno{
string nome;
double nota_prova1;
double nota_prova2;
int matricula;
}
 Busca em arranjos
• Neste caso prático, o problema da busca
em arranjo consiste em encontrar em
qual posição do arranjo a está o aluno
com número de matrícula x

x 726922 a aluno 0 aluno 1 aluno 2 aluno 3 aluno 4 aluno 5 aluno 6

int busca(int chave, Aluno a[], int n);

?
 Busca em arranjos
• Para apresentação didática dos
métodos, consideraremos arranjos de
int onde o próprio valor do int é sua
chave.

x 9 a 6 3 8 5 9 2 1

a[0] a[1] a[2] a[3] a[4] a[5] a[6]

7

int busca(int chave, int a[], int n);

Elemento 9 está na
4 posição 4 do arranjo
 Busca Sequencial

• O método mais simples para busca é, a

partir do primeiro elemento, pesquisar
sequencialmente um-a-um até
encontrar a chave procurada.
int buscaSequencial(int chave, int a[], int n){
for (int i=0; i<n; i++)
{
if (a[i] == chave)
{
return i;
}
}
return -1;
}
A função procura o elemento chave no arranjo a, que
tem tamanho n

int buscaSequencial(int chave, int a[], int n){

for (int i=0; i<n; i++)
{
if (a[i] == chave)
{
return i;
}
}
return -1;
}

a 6 3 8 5 9 2 1 chave 9

a[0] a[1] a[2] a[3] a[4] a[5] a[6]

n 7
Ela retornará um int que dirá em qual posição do
arranjo a está o elemento chave
4
int buscaSequencial(int chave, int a[], int n){
for (int i=0; i<n; i++)
{
if (a[i] == chave)
{
return i;
}
}
return -1;
}

a 6 3 8 5 9 2 1 chave 9

a[0] a[1] a[2] a[3] a[4] a[5] a[6]

n 7
 A estrutura de repetição ocorre com i de 0 até n-1
para percorrer da primeira até a última posição a[i]
do arranjo a
int buscaSequencial(int chave, int a[], int n){
for (int i=0; i<n; i++)
{
if (a[i] == chave)
{
return i;
}
}
return -1;
} 0, 1, 2, 3, 4, 5, 6

a 6 3 8 5 9 2 1 chave 9

a[0] a[1] a[2] a[3] a[4] a[5] a[6]

n 7

a[i] a[i] a[i] a[i] a[i] a[i] a[i]

i
Comparamos cada elemento do arranjo com o
elemento chave.

int buscaSequencial(int chave, int a[], int n){

for (int i=0; i<n; i++)
{
if (a[i] == chave)
{
return i;
}
}
return -1;
}

a 6 3 8 5 9 2 1 chave 9

a[0] a[1] a[2] a[3] a[4] a[5] a[6]

n 7

a[i]
i 0
Comparamos cada elemento do arranjo com o
elemento chave.

int buscaSequencial(int chave, int a[], int n){

for (int i=0; i<n; i++)
{
if (a[i] == chave)
{
return i;
}
}
return -1;
}

a 6 3 8 5 9 2 1 chave 9

a[0] a[1] a[2] a[3] a[4] a[5] a[6]

n 7

a[i]
i 1
Comparamos cada elemento do arranjo com o
elemento chave.

int buscaSequencial(int chave, int a[], int n){

for (int i=0; i<n; i++)
{
if (a[i] == chave)
{
return i;
}
}
return -1;
}

a 6 3 8 5 9 2 1 chave 9

a[0] a[1] a[2] a[3] a[4] a[5] a[6]

n 7

a[i]
i 2
Comparamos cada elemento do arranjo com o
elemento chave.

int buscaSequencial(int chave, int a[], int n){

for (int i=0; i<n; i++)
{
if (a[i] == chave)
{
return i;
}
}
return -1;
}

a 6 3 8 5 9 2 1 chave 9

a[0] a[1] a[2] a[3] a[4] a[5] a[6]

n 7

a[i]
i 3
Comparamos cada elemento do arranjo com o
elemento chave.

int buscaSequencial(int chave, int a[], int n){

for (int i=0; i<n; i++)
{
if (a[i] == chave)
{
return i;
}
}
return -1;
}

a 6 3 8 5 9 2 1 chave 9

a[0] a[1] a[2] a[3] a[4] a[5] a[6]

n 7

a[i]
i 4
Se o elemento chave foi encontrado, o valor de i, que
tem sua posição nesta iteração da repetição, é
retornado.
int buscaSequencial(int chave, int a[], int n){
for (int i=0; i<n; i++)
{
if (a[i] == chave)
{
true
return i;
}
}
return -1;
}

a 6 3 8 5 9 2 1 chave 9

a[0] a[1] a[2] a[3] a[4] a[5] a[6]

n 7

a[i]
i 4
 Se o elemento chave não foi encontrado e a
comparação deu false, passamos para a próxima
iteração de repetição.
int buscaSequencial(int chave, int a[], int n){
for (int i=0; i<n; i++)
{
if (a[i] == chave)
{
false
return i;
}
}
return -1;
}

a 6 3 8 5 9 2 1 chave 9

a[0] a[1] a[2] a[3] a[4] a[5] a[6]

n 7

a[i]
i 1
 Se em nenhuma das iterações o elemento foi
encontrado, saímos do for e retornamos -1. O
retorno de -1 avisa para a função chamadora que o
elemento não foi encontrado.
int buscaSequencial(int chave, int a[], int n){
for (int i=0; i<n; i++)
{
if (a[i] == chave)
{
return i;
}
}
return -1;
}

a 6 3 8 5 9 2 1 chave 9

a[0] a[1] a[2] a[3] a[4] a[5] a[6]

n 7

a[i]
i 7
 Análise

• Em relação ao número de comparações:

• Melhor caso: Quando o elemento que
procuramos é o primeiro do arranjo
• Pior caso: o elemento que procuramos
é o último do arranjo ou não está no
arranjo
 Análise
• Em relação ao número de comparações:
• Melhor caso: f(n) = 1
• Pior caso: f(n) = n
• Caso médio: f(n) = (n+1)/2
• Estas análises assumem que todas
as buscas encontrarão o elemento
• Pesquisa sem sucesso: f(n) = n
 Análise

• Em notação O, podemos dizer que em

relação ao número de comparações, a
busca sequencial é O(n) para todos os
casos, com exceção do melhor caso, no
qual o algoritmo é O(1)
 Busca Binária

• É um método mais eficiente que a busca

sequencial
• Porém, a busca binária requer que os
elementos estejam mantidos em ordem
 Busca Binária
• A cada iteração, pesquisamos o elemento do
meio
• Se a chave é maior, repetimos o processo
na primeira metade
• Senão, repetimos este passo na segunda
metade
• A busca binária é um método interessante
pois remete a como buscamos palavras em
um dicionário
 Exemplo
a 1 2 3 5 6 8 9 chave 8

a[0] a[1] a[2] a[3] a[4] a[5] a[6]

Procuraremos o elemento 8 no arranjo a

 Exemplo
a 1 2 3 5 6 8 9 chave 8

a[0] a[1] a[2] a[3] a[4] a[5] a[6]

i 3

Comparamos a chave com o elemento do meio

6/2 = 3
Como a chave é maior que a[3] ou 5, sabemos agora
que só precisamos procurar do lado direito do arranjo
 Exemplo
a 1 2 3 5 6 8 9 chave 8

a[0] a[1] a[2] a[3] a[4] a[5] a[6]

i 5
a 1 2 3 5 6 8 9

a[0] a[1] a[2] a[3] a[4] a[5] a[6]

Desconsideramos então os elementos de a[0] a a[3] do

arranjo e repetimos o procedimento.
O elemento do meio entre os que sobraram agora é
a[5].
 Exemplo
a 1 2 3 5 6 8 9 chave 8

a[0] a[1] a[2] a[3] a[4] a[5] a[6]

i 5
a 1 2 3 5 6 8 9

a[0] a[1] a[2] a[3] a[4] a[5] a[6]

Como o elemento do meio agora é igual à chave, o

algoritmo retorna o valor de i.
Com a busca binária, já encontramos o elemento na
segunda comparação.
int buscaBinaria(int chave, int a[], int n){
int i;
int esq = 0;
int dir = n-1;
do {
i = (esq + dir)/2;
if (chave > a[i]){
esq = i + 1;
} else {
dir = i - 1;
}
} while (chave != a[i] && esq <= dir);
if (chave == a[i]){
return i;
} else {
return -1;
}
}
Similarmente à busca sequencial, a função procura o
elemento chave no arranjo a, que tem tamanho n
int buscaBinaria(int chave, int a[], int n){
int i;
int esq = 0;
int dir = n-1;
do {
i = (esq + dir)/2;
if (chave > a[i]){
esq = i + 1;
} else {
dir = i - 1;
}
} while (chave != a[i] && esq <= dir);
if (chave == a[i]){
return i;
} else {
return -1;
}
}

a 1 2 3 5 6 8 9 chave 6

a[0] a[1] a[2] a[3] a[4] a[5] a[6]

n 7
O índice i marcará o elemento sendo comparado,
assim como no for da busca sequencial.
int buscaBinaria(int chave, int a[], int n){
int i;
int esq = 0;
int dir = n-1;
do {
i = (esq + dir)/2;
if (chave > a[i]){
esq = i + 1;
} else {
dir = i - 1;
}
} while (chave != a[i] && esq <= dir);
if (chave == a[i]){
return i;
} else {
return -1;
}
}

a 1 2 3 5 6 8 9 chave 6

a[0] a[1] a[2] a[3] a[4] a[5] a[6]

n 7
Os índices esq e dir marcarão os limites de onde a
busca está sendo feita.
int buscaBinaria(int chave, int a[], int n){
int i;
int esq = 0;
int dir = n-1;
do {
i = (esq + dir)/2;
if (chave > a[i]){
esq = i + 1;
} else {
dir = i - 1;
}
} while (chave != a[i] && esq <= dir);
if (chave == a[i]){
return i;
} else {
return -1;
}
}

esq i dir

a 1 2 3 5 6 8 9 chave 6

a[0] a[1] a[2] a[3] a[4] a[5] a[6]

n 7
Inicialmente, a busca será feita entre os elementos
a[0] e a[n-1], ou a[6]
int buscaBinaria(int chave, int a[], int n){
int i;
int esq = 0;
int dir = n-1;
do {
i = (esq + dir)/2;
if (chave > a[i]){
esq = i + 1;
} else {
dir = i - 1;
}
} while (chave != a[i] && esq <= dir);
if (chave == a[i]){
return i;
} else {
return -1;
}
}

esq 0 i dir 6

a 1 2 3 5 6 8 9 chave 6

a[0] a[1] a[2] a[3] a[4] a[5] a[6]

n 7

a[esq] a[dir]
Entramos em uma estrutura de repetição onde a cada
passo um elemento i será comparado.
int buscaBinaria(int chave, int a[], int n){
int i;
int esq = 0;
int dir = n-1;
do {
i = (esq + dir)/2;
if (chave > a[i]){
esq = i + 1;
} else {
dir = i - 1;
}
} while (chave != a[i] && esq <= dir);
if (chave == a[i]){
return i;
} else {
return -1;
}
}

esq 0 i dir 6

a 1 2 3 5 6 8 9 chave 6

a[0] a[1] a[2] a[3] a[4] a[5] a[6]

n 7

a[esq] a[dir]
O índice i aponta então para o elemento do meio do
arranjo.
int buscaBinaria(int chave, int a[], int n){
int i;
int esq = 0;
int dir = n-1;
do {
i = (esq + dir)/2;
if (chave > a[i]){
esq = i + 1;
} else {
dir = i - 1;
}
} while (chave != a[i] && esq <= dir);
if (chave == a[i]){
return i;
} else {
return -1;
}
}

esq 0 i 3 dir 6

a 1 2 3 5 6 8 9 chave 6

a[0] a[1] a[2] a[3] a[4] a[5] a[6]

n 7

a[esq] a[i] a[dir]

A chave 6, é maior que o elemento do meio 5.

int buscaBinaria(int chave, int a[], int n){

int i;
int esq = 0;
int dir = n-1;
do {
i = (esq + dir)/2;
if (chave > a[i]){
esq = i + 1;
} else {
dir = i - 1;
}
} while (chave != a[i] && esq <= dir);
if (chave == a[i]){
return i;
} else {
return -1;
}
}

esq 0 i 3 dir 6

a 1 2 3 5 6 8 9 chave 6

a[0] a[1] a[2] a[3] a[4] a[5] a[6]

n 7

a[esq] a[i] a[dir]

 Por isto, pesquisaremos agora apenas na metade à
direita de i e, a partir de agora, a metade à esquerda
será desconsiderada pelo algoritmo.
int buscaBinaria(int chave, int a[], int n){
int i;
int esq = 0;
int dir = n-1;
do {
i = (esq + dir)/2;
if (chave > a[i]){
esq = i + 1;
} else {
dir = i - 1;
}
} while (chave != a[i] && esq <= dir);
if (chave == a[i]){
return i;
} else {
return -1;
}
}

esq 4 i 3 dir 6

a 1 2 3 5 6 8 9 chave 6

a[0] a[1] a[2] a[3] a[4] a[5] a[6]

n 7

a[i] a[esq] a[dir]

Se a chave fosse menor que a[i], o contrário
ocorreria, e a metade à direita passaria a ser
desconsiderada.
int buscaBinaria(int chave, int a[], int n){
int i;
int esq = 0;
int dir = n-1;
do {
i = (esq + dir)/2;
if (chave > a[i]){
esq = i + 1;
} else {
dir = i - 1;
}
} while (chave != a[i] && esq <= dir);
if (chave == a[i]){
return i;
} else {
return -1;
}
}

esq 4 i 3 dir 6

a 1 2 3 5 6 8 9 chave 6

a[0] a[1] a[2] a[3] a[4] a[5] a[6]

n 7

a[i] a[esq] a[dir]

Se a chave não é o elemento a[i], a repetição deve
continuar pois o elemento i não foi encontrado.
int buscaBinaria(int chave, int a[], int n){
int i;
int esq = 0;
int dir = n-1;
do {
i = (esq + dir)/2;
if (chave > a[i]){
esq = i + 1;
} else {
dir = i - 1;
}
} while (chave != a[i] && esq <= dir);
if (chave == a[i]){
return i;
} else {
return -1;
}
}

esq 4 i 3 dir 6

a 1 2 3 5 6 8 9 chave 6

a[0] a[1] a[2] a[3] a[4] a[5] a[6]

n 7

a[i] a[esq] a[dir]

 Se o índice esq é menor ou igual a dir, a repetição
deve ser continuar pois isto indica o arranjo inteiro não
foi pesquisado
int buscaBinaria(int chave, int a[], int n){
int i;
int esq = 0;
int dir = n-1;
do {
i = (esq + dir)/2;
if (chave > a[i]){
esq = i + 1;
} else {
dir = i - 1;
}
} while (chave != a[i] && esq <= dir);
if (chave == a[i]){
return i;
} else {
return -1;
}
}

esq 4 i 3 dir 6

a 1 2 3 5 6 8 9 chave 6

a[0] a[1] a[2] a[3] a[4] a[5] a[6]

n 7

a[i] a[esq] a[dir]

O índice i marca o elemento do meio entre os que
ainda estão sendo considerados.
int buscaBinaria(int chave, int a[], int n){
int i;
int esq = 0;
int dir = n-1;
do {
i = (esq + dir)/2;
if (chave > a[i]){
esq = i + 1;
} else {
dir = i - 1;
}
} while (chave != a[i] && esq <= dir);
if (chave == a[i]){
return i;
} else {
return -1;
}
}

esq 4 i 5 dir 6

a 1 2 3 5 6 8 9 chave 6

a[0] a[1] a[2] a[3] a[4] a[5] a[6]

n 7

a[esq] a[i] a[dir]

 Como a[5] (ou 8) é maior que a chave 6 que
procuramos, alteramos dir para restringir a busca ao
lado esquerdo do arranjo.
int buscaBinaria(int chave, int a[], int n){
int i;
int esq = 0;
int dir = n-1;
do {
i = (esq + dir)/2;
if (chave > a[i]){
esq = i + 1;
} else {
dir = i - 1;
}
} while (chave != a[i] && esq <= dir);
if (chave == a[i]){
return i;
} else {
return -1;
}
}

esq 4 i 5 dir 4

a 1 2 3 5 6 8 9 chave 6

a[0] a[1] a[2] a[3] a[4] a[5] a[6]

n 7

a[esq] a[i]
a[dir]
 O elemento a[i] ainda não é a chave que
procuramos e os índices esq e dir não se cruzaram
indicando que todo o arranjo já foi percorrido.
int buscaBinaria(int chave, int a[], int n){
int i;
int esq = 0;
int dir = n-1;
do {
i = (esq + dir)/2;
if (chave > a[i]){
esq = i + 1;
} else {
dir = i - 1;
}
} while (chave != a[i] && esq <= dir);
if (chave == a[i]){
return i;
} else {
return -1;
}
}

esq 4 i 5 dir 4

a 1 2 3 5 6 8 9 chave 6

a[0] a[1] a[2] a[3] a[4] a[5] a[6]

n 7

a[esq] a[i]
a[dir]
Na próxima iteração, o elemento do meio marcado
por i é o único elemento ainda não considerado.
int buscaBinaria(int chave, int a[], int n){
int i;
int esq = 0;
int dir = n-1;
do {
i = (esq + dir)/2;
if (chave > a[i]){
esq = i + 1;
} else {
dir = i - 1;
}
} while (chave != a[i] && esq <= dir);
if (chave == a[i]){
return i;
} else {
return -1;
}
}

esq 4 i 4 dir 4

a 1 2 3 5 6 8 9 chave 6

a[0] a[1] a[2] a[3] a[4] a[5] a[6]

n 7

a[esq] a[i]
a[dir]
Como a chave não é maior que a[i] (ela é igual),
deslocamos o índice dir mais uma vez para indicar
que não há mais elementos a se pesquisar.
int buscaBinaria(int chave, int a[], int n){
int i;
int esq = 0;
int dir = n-1;
do {
i = (esq + dir)/2;
if (chave > a[i]){
esq = i + 1;
} else {
dir = i - 1;
}
} while (chave != a[i] && esq <= dir);
if (chave == a[i]){
return i;
} else {
return -1;
}
}

esq 4 i 4 dir 4

a 1 2 3 5 6 8 9 chave 6

a[0] a[1] a[2] a[3] a[4] a[5] a[6]

n 7

a[dir] a[esq]
a[i]
Como a chave foi encontrada e não há mais elementos
para se pesquisar, nenhuma das condições para se
continuar o laço é verdadeira.
int buscaBinaria(int chave, int a[], int n){
int i;
int esq = 0;
int dir = n-1;
do {
i = (esq + dir)/2;
if (chave > a[i]){
esq = i + 1;
} else {
dir = i - 1;
}
} while (chave != a[i] && esq <= dir);
if (chave == a[i]){
return i;
} else {
return -1;
}
}

esq 4 i 4 dir 4

a 1 2 3 5 6 8 9 chave 6

a[0] a[1] a[2] a[3] a[4] a[5] a[6]

n 7

a[dir] a[esq]
a[i]
Como o elemento i que pesquisamos é a chave,
retornamos este índice.
int buscaBinaria(int chave, int a[], int n){
int i;
int esq = 0;
int dir = n-1;
do {
i = (esq + dir)/2;
if (chave > a[i]){
esq = i + 1;
} else {
dir = i - 1;
}
} while (chave != a[i] && esq <= dir);
if (chave == a[i]){
return i;
} else {
return -1;
}
}

esq 4 i 4 dir 4

a 1 2 3 5 6 8 9 chave 6

a[0] a[1] a[2] a[3] a[4] a[5] a[6]

n 7

a[dir] a[esq]
a[i]
Se o elemento i não fosse a chave, seria porque o
elemento não estava no arranjo. Deveríamos então
retornar -1.
int buscaBinaria(int chave, int a[], int n){
int i;
int esq = 0;
int dir = n-1;
do {
i = (esq + dir)/2;
if (chave > a[i]){
esq = i + 1;
} else {
dir = i - 1;
}
} while (chave != a[i] && esq <= dir);
if (chave == a[i]){
return i;
} else {
return -1;
}
}

esq 4 i 4 dir 4

a 1 2 3 5 6 8 9 chave 6

a[0] a[1] a[2] a[3] a[4] a[5] a[6]

n 7

a[dir] a[esq]
a[i]
 Análise

• A busca binária é um método

interessante pois remete a como
buscamos palavras em um dicionário
 Análise
• Em relação ao número de comparações
temos um cenário similar à busca
sequencial:
• Melhor caso: Quando o elemento que
procuramos é o primeiro que testamos
(meio do arranjo)
• Pior caso: o elemento que procuramos é
o último que comparamos ou quando o
elemento não está no arranjo
 Análise

• Em relação ao número de comparações:

• Melhor caso: f(n) = O(1)
• Pior caso: f(n) = O(log n)
• Caso médio: f(n) = O(log n)
 Análise
• Em notação O, mesmo os piores casos são
O(log n) pois a cada passo o algoritmo
elimina metade do problema.
• n → n/2 → n/22 → 3
n/2 → …→1
• (n/2k = 1 → k = log n passos)
• Isto o deixa muito mais eficiente em
relação à busca sequencial O(n)
• Se n = 1.000.000, log n = 6
 Análise
• Uma desvantagem é que manter o arranjo
ordenado pode ter um custo muito alto
• Isto torna este método mais vantajoso
para aplicações pouco dinâmicas
• Este é justamente o caso de
dicionários
• Estudaremos nas aulas seguintes como
manter os arranjos ordenados
 Estudaremos nas Seções seguintes métodos para os arranjos ordenados.
A Figura 15.4 apresenta o tempo gasto pelos algoritmos de busca sequencial e busca binária

Experimentos
para se encontrar um elemento em um arranjo. A Figura 15.4(a) apresenta resultados para
arranjos com até 3000 elementos enquanto a Figura 15.4(b) apresenta resultados para arranjos
com até 80 mil elementos. Como a busca sequencial tem custo O(n) e a busca binária tem custo
O(log n), vemos que à medida que os arranjos ficam maiores, a busca binária se torna cada vez
mais vantajosa. Porém, é possível que para arranjos pequenos, a busca sequencial seja mais
vantajosa. Nestes experimentos, isto ocorre para arranjos com menos de 350 elementos.
−6 −5
x 10 x 10
1.8 1.5
Busca sequencial Busca sequencial
Busca binária Busca binária
1.6

1.4

1.2 1
Tempo (segundos)

Tempo (segundos)
1

0.8

0.6 0.5

0.4

0.2

0 0
0 500 1000 1500 2000 2500 3000 0 1 2 3 4 5 6 7 8
Tamanho do arranjo Tamanho do arranjo 4
x 10

(a) Arranjos menores (b) Arranjos maiores

Figura 15.4: Tempo necessário pelos algoritmos de busca para se encontrar um elemento em
arranjos de vários tamanhos.
 Exercício

• Desenhar um arranjo com 10 números

aleatórios entre 1 e 50
• Escolher um elemento chave
• Redesenhar este arranjo várias vezes indicando
onde estaria o elemento a[i] em cada passo
de uma busca sequencial
• Redesenhar este arranjo várias vezes indicando
onde estariam os elementos a[i], a[esq] e
a[dir] em cada passo de uma busca binária
Programação de Computadores
Busca em Arranjos
Alan R R Freitas
Programação de Computadores
Comparando Algoritmos
Alan R R Freitas