binária x sequencial

Pesquisa sequencial e pesquisa bin´ aria Armando Matos
Departamento de Ciˆencia de Computadores
Universidade de Porto

2008

2 problemas importantes. . .

Pesquisa: Procurar um valor numa lista ou, por exemplo, num ficheiro pesquisa 5 em [8,2,1,5,2,6] → True
Ordena¸c˜ao: ordenar uma lista.
Exemplo, ordem n˜ao decrescente:
[8,2,1,5,2,6] → [1,2,2,5,6,8]

Outline

Pesquisa

Pesquisa sequˆencial

Pesquisa sequˆencial

Seja x: o valor que se vai procurar a: a lista onde se vai procurar x;
´ındices de a: 0 a n − 1. procura(x,a) ⇒ bool
M´etodo:
x ´e comparado sucessivamente com a[0], a[1],. . . , a[n-1].
Se x for igual a algum dos a[i], retorna-se True.
Sen˜ao, retorna-se False.

Pesquisa sequˆencial, fun¸c˜ao em python

# p r o c u r a x na l i s t a a def procura (x , a ) : n=l e n ( a ) i =0 w h i l e i i2), pela manuten¸c˜ao do invariante do ciclo, x n˜ao est´a na lista.

Pesquisa bin´aria – termina¸c˜ao da fun¸c˜ao

Notas sobre a termina¸c˜ao da fun¸c˜ao:
Os ´ındices em que x pode “estar” s˜ao i1, i1+1,. . . , i2.
Seja num=i2-i1+1 o n´ umero desses ´ındices.
A prova de termina¸c˜ao ´e baseada no facto de num diminuir de cada vez que o teste das linhas 7 e 9 ´e efectuado e isso prova-se com os seguintes factos i1 ≤ m ≤ i2 onde m resulta da atribui¸c˜ao m=(i1+i2)/2.
A atribui¸c˜ao i2=m-1 (linha 8) reduz num, pois, com o valor inicial da i2, m − 1 < m ≤ i2
A atribui¸c˜ao i1=m+1 (linha 10) reduz num, pois, com o valor inicial da i1, i1 ≤ m < m + 1

Eficiˆencia da pesquisa bin´aria

Vamos usar como medida de eficiˆencia no tempo de execu¸c˜ao o n´ umero c(n) de compara¸c˜ oes entre x e a[i], contando as linhas
7 e 9 como uma s´o compara¸c˜ao, (compara¸c˜ao entre x e a[m])
Vamos determinar o n´ umero de compara¸c˜ oes no pior caso (quando x n˜ao est´a na lista)

Eficiˆencia da pesquisa bin´aria
Para simplificar, supomos que n=len(a) ´e da forma n = 2p − 1.
Ap´os uma divis˜ao a “meio”, o n´