[Resolvido] Busca Binária na Lista Encadeada

[Linguagem utilizada: C++]

Meu professor de Estrutura de Dados passou duas questões para resolvermos, que são:

1) Realizar a ordenação de uma lista encadeada (simples ou dupla).

2) Realizar busca binária na lista ordenada

Obs: não usar vetor!

Bom, a 1ª resolvi tranquilo, como segue o código abaixo:

 int aux;
 for (NodePtr p1 = L.first(); p1 != NULL; p1 = L.next(p1))
 for (NodePtr p2 = L.next(p1); p2 != NULL; p2 = L.next(p2))
 if (L.retrieve(p1) > L.retrieve(p2))
 {
 aux = L.retrieve(p1);
 L.setItem(p1, L.retrieve(p2));
 L.setItem(p2, aux);
 }

// L.first() - retorna o 1º nodo da lista;

// L.next(apontador) - retorna o proximo item do apontador // L.retrieve(apontador) - retorna o item contido no endereço do apontador // L.setItem(apontador, L.retrieve(p2)) - atrubui ao apontador o item passado

Porém, não consigo imaginar como fazer a segunda. Sei que um código para um vetor seria tipo assim:

 int meio, esq, dir; // esq = esquerda; dir = direita;
 esq = 1;
 dir = size; // size é o tamanho(nº de elementos) da lista

 while (esq < dir)
 {
 meio = (esq + dir)/2;
 if (L[meio] == n)
 return meio;
 else
 if (L[meio] < n)
 esq = meio + 1;
 else
 dir = meio - 1;
 }

A lógica das duas (tanto vetor quanto lista) é ir dividindo as partes ao meio e ver se o item está na posição do meio, mas como saber o meio de uma lista? não existe essa possibilida sem transformá-la em um vetor. Então, gostaria de que, se possível, me ajudassem a entender como fazer essa busca binária na lista, lembrando que não quero o código pronto, quero entender a lógica e colocar a mão na massa.

Desde já, muito Obrigado.