Apanhando para uma busca binária por 1h

Como não fazer uma busca binária

Depois de aprender sobre slices no post passado, segui para o próximo problema querendo usar minha minúscula caixa de ferramentas.
Por curiosidade, o leetcode que vou resolver é esse: Search Insert Position

Como a descrição diz que a complexidade deve ser O(log n) nem tentei percorrer o array. Eu também já tinha na cabeça a ideia de verificar o meio do array e eliminar metade dele. Conceitualmente parecia um problema simples pra mim, mas na prática a teoria é outra.

A primeira coisa que tentei foi usar um slice mutável do array nums:

//Esse código não compila, se atenha ao raciocíno
pub fn search_insert(nums: Vec<i32>, target: i32) -> i32 {
    let mut length = nums.len();
    let mut array = &nums[..length];
    loop {
        if array[length/2] == target {
            return length/2;
        }
        if array[length/2] > target {
            array = &array[..(length/2)];
        }else{
            array = &array[(length/2)..];
        }
        if length == 1 {
            // O que devia retornar?
        }else{
            length = array.len();
        }
    }
}

Percorri o array até onde o alvo está, agora só tenho que retornar o índice!

Foi quando eu percebi que eu perdi a posição no array original. Quando encontro o target, ele está no índice 0 do slice, mas isso não me ajuda em nada.

Talvez tenha alguma forma de resolver dessa forma, mas com certeza não é idiomático.

Voltando alguns passos

Tenho que percorrer pedaços cada vez menores do array original sem perder o índice absoluto.
A forma que parece ser mais comum de fazer isso é ter um limite inferior e superior (esquerda e direita, tanto faz) variáveis.

let mut low = 0;
let mut high = nums.len();

Basta verificar o elemento exatamente no meio de low e high

let mid = low + (high-low)/2;
if nums[mid] == target {
    return mid;
}
if nums[mid] > target {
    high = mid;
}else{
    low = mid+1;
}

Dessa forma, low e high vão se aproximando. Quando eles se tocam, significa que o array foi totalmente percorrido.

while low < high {
    //Código anterior
    let mid = low + (high-low)/2;
    if nums[mid] == target {
        return mid;
    }
    if nums[mid] > target {
        high = mid;
    }else if nums[mid] < target {
        low = mid+1;
    }
}

Note que mid aponta para o elemento do meio em arrays com número ímpar de elementos. Em arrays com número par, mid aponta para o último elemento da primeira metade.
nums = [10,20,30,40] -> mid = 1
Por isso low recebe mid+1 diferentemente de high.

Por fim...

Queria só escrever minha linha de raciocínio nesse caso. Pois gastei um tempo danado "debugando" na minha mente para entender o que tinha que fazer e como era a maneira certa de iterar no array e quando o loop devia parar, se tinha que retornar low, high, mid.
Depois de passar por essa experiência aprendi que:

• Ver alguém explicar a resolução não é o mesmo que fazer.
• Ainda existe muito que eu não sei.
• Na dúvida não use alguma funcionalidade única da sua linguagem.
• Na dúvida use ponteiros.