Considere o vetor ordenado V = [3, 8, 15, 19, 24, 30, 42]. Usando o algoritmo de pesquisa linear, qual é o número de comparações realizadas para encontrar o elemento 24?

Gabarito

Certo

Comentário do professor

Temos o vetor V = [3, 8, 15, 19, 24, 30, 42] e o alvo é o valor 24. Na pesquisa linear os elementos são verificados um a um, na ordem, até encontrar o alvo; o processo termina assim que o valor é localizado.

Comparação 1: verifica 3 — não coincide com 24.

Comparação 2: verifica 8 — não coincide com 24.

Comparação 3: verifica 15 — não coincide com 24.

Comparação 4: verifica 19 — não coincide com 24.

Comparação 5: verifica 24 — coincide; busca encerrada.

Como o elemento foi encontrado na quinta posição, o número de comparações realizadas é \(5\). De modo geral, se o alvo está na posição \(i\), a pesquisa linear exige \(C=i\) comparações; no pior caso \(C=n\) e, em média, \(C\approx (n+1)/2\).