El problema:

Dado un arreglo de enteros nums ordenado de forma ascendente, y un entero target, escribe una función para buscar target en nums. Si target existe, entonces retorna su índice. De lo contrario, retorna -1. Debes escribir un algoritmo con complejidad de tiempo O(log n).

Para este problema se me ocurrieron tres soluciones:

La solución “Ilegal”

var search = function (nums, target) {
    return nums.indexOf(target) // Me rehuso a escribir más código
};

Tecnicamente hablando esta solución está bien, sin embargo, en una entrevista técnica real no creo que el reclutador lo deje pasar.

La solución de “fuerza bruta”

function search(nums, target) {
    let left = 0;
    let right = nums.length -1;
    while(left <= right) {
        if(nums[left] === target) {
            return left;
        }
        if(nums[right] === target) {
            return right;
        }
        if(nums[left] < target) {
            left++
        }
        if(nums[right] > target) {
            right--
        }
    }
    return -1;
};

Esta no es una solución de fuerza bruta real en su totalidad, pero como no estamos haciendo busqueda binaria real, sigue sin ser una solución optima, veamos linea por linea:

function search(nums, target) {
    let left = 0; // Puntero a la izquierda
    let right = nums.length -1; // Puntero a la derecha
    while(left <= right) {
        if(nums[left] === target) { // Si encontramos el número con el puntero izquierdo, lo retornamos
            return left;
        }
        if(nums[right] === target) { // Si encontramos el número con el puntero derecho, lo retornamos
            return right;
        }
        if(nums[left] < target) { // Si el valor en left es menor que target, movemos el puntero izquierdo una posición a la derecha
            left++
        }
        if(nums[right] > target) { // Si el valor en right es mayor que target, movemos el puntero derecho una posición a la izquierda
            right--
        }
    }
    return -1;
};

En el mejor de los casos, encontramos el objetivo en los primeros índices, pero si el objetivo está justo en el medio, entonces estamos perdiendo mucho tiempo.

Aunque esta no es objetivamente una mala solución al problema, podríamos implementar algo aún más sencillo y con mejor rendimiento.

La solución Optima”

var search = function (nums, target) {
    let left = 0; // Puntero a la izquierda
    let right = nums.length - 1; // Puntero a la derecha
    while (left <= right) { // Mientras left sea menor o igual a right, seguimos buscando
        const mid = Math.floor((left + right) / 2); // Obtenemos el índice central entre los dos punteros
        if (nums[mid] === target) { // Si el valor en mid es el objetivo, retornamos mid
            return mid;
        } else if (nums[mid] < target) { // Si nums[mid] es menor que target, movemos left a mid + 1
            left = mid + 1;
        } else {
            right = mid - 1; // Si no, movemos right a mid - 1
        }
    }
    return -1; // No encontramos el objetivo
};