Busca binaria

No algoritmo de busca binária, você precisa saber o limite inferior e o limite superior para fazer a busca. Antes de fazer a busca binária você precisa calcular esses limites. Então precisa criar um algoritmo novo que chama encontrarLimites. Ele é mais ou menos assim: encontrarLimite (vetor, chave) { inf = 0 sup = 1 while (vetor[sup] < chave) { inf = sup sup = sup * 2 } return (buscaBinaria (vetor, inf, sup, chave)) } Já que a gente não sabe o tamanho do vetor, mas sabe que ele é ordenado, a gente dobra o limite superior até ele passar do valor da chave que estamos procurando. Quando ele passar, sabemos que a chave não está além disso, então colocamos isso como o limite superior da busca binária. A complexidade desse algoritmo é O(log p), mesmo que da busca binária, sendo que p é o índice da chave que estamos procurando.

Via de regra a complexidade de um algoritmo é calculada a partir do número de iterações aninhadas, a grosso modo seria o número de loops aninhados necessários para se alcançar o ponto de parada no pior cenário. A notação utilizada é a O(n). Então, por exemplo, se seu algoritmo irá ter dois loops (for, while, etc...) aninhados e o pior caso seja passar por todos elementos do loop mais externo e para cada ítem externo você também precisa passar por todos elementos do loop interno a sua complexidade seria O(n^2) - lê-se "O de n ao quadrado". Existe muito mais coisa por trás disso, pq a complexidade pode ser logaritmica, cúbica, etc mas isso depende de cada caso. Não analisei o exercício que você colocou mas espero ter ajudado.

Essa é para o Batman.... Realmente estou contigo. Boa sorte! :-)