Busca binária

A busca binária tem o mesmo objetivo da busca linear, seu tempo de busca é muito mais otimizado que o da busca linear, no entanto, para seu funcionamento, o vetor deve estar ordenado.
Exemplo de vetor ordenado: vetor[10] = {0,1,2,3,4,5,6,7,8,9}; 
A busca binária localiza o meio do vetor com a fórmula (Inicio + Fim) / 2, sendo Inicio a primeira posição do vetor e Fim a ultima posição do vetor. Levando em consideração o exemplo vetor[10] teríamos: (1+10) /2 = 5,5. Em C este valor seria passado para 5, pois ao armazena-lo como inteiro (int) as casas decimais são ignoradas.
Tendo em mãos o meio (5) do vetor ordenado o algoritmo verifica se o valor procurando é ele, se não for ele verificará se é maior ou menor que ele. Sendo maior, a busca será feita apenas na parte direita da metade, se menor, a busca será realizada na parte da esquerda:

O vetor vai sendo divido até que o valor seja encontrado. Se o valor não existir a condição de parada será quando o inicio e o fim for igual e nada foi encontrado. Exemplo do algoritmo de busca binária e sua chamada:

#define TAM 10
//BUSCA BINÁRIA
int buscaBinaria(int vetor[], int tamanho, int valor)
{
    int meio, i, ini = 0, fim = tamanho-1;
    while(ini <= fim)
    {
        meio = (ini + fim) / 2; //encontrando o meio do vetor
        if(valor == vetor[meio]) //valor encontrado?
            return meio; //retorna posição do valor encontrado
        else if(valor < vetor[meio])
            fim = meio - 1;
        else
            ini = meio + 1;
    }
    return -1; //valor não enconrado
}

int main(int argc, char *argv[])
{
    int v[TAM] = {0,1,2,3,4,5,6,7,8,9}, i, indice;

    indice = buscaBinaria(v, TAM, 8);
    printf("\nO valor procurado esta na posicao %d", indice);

    getch();
    return 0;
}

Veja também o artigo sobre Busca linear ou busca sequencial.