Esta búsqueda binaria funciona con números, pero no funciona con picaduras.
function binary_search(Array, key) { var middleIndex = Math.floor(Array.length / 2) var middleValue = numberArray[middleIndex] //base case key = middle element if (middleValue === key) return true else if (middleValue < key && Array.length > 1) { return binary_search(Array.splice(middleIndex, Array.length), key) } else if (middleValue > key && Array.length > 1) { return binary_search(Array.splice(0, middleIndex), key) } else return false }Si le doy números, funciona:
console.log(binary_search([5,7,12,16,36,39,42,56,71], 36)) output: truePero no con cadenas:
console.log(binary_search(['cat', 'dog', 'bird', 'fish'], 'dog')) result : flaseEntiendo que la matriz debe estar preordenada para que esto funcione, pero ¿cómo hacer esto con cadenas?
tal como dices
Entiendo que la matriz debe estar preordenada para que esto funcione
La matriz de cadenas que está pasando no está ordenada, por lo que la búsqueda binaria no será posible. Si lo ordenas primero
['bird', 'cat', 'dog', 'fish'] entonces su enfoque actual ya funcionará, principalmente , porque === compara cadenas correctamente, y < y > también compara cadenas lexiográficamente (funciona tanto para números como para cadenas), con algunas advertencias:
slice para extraer un segmento de una matriz, no splice , que eliminará elementos de la matriz (¡una mutación!) y devolverá una matriz de esos elementos devueltos (no muy intuitivo)numberArray en el alcance, y tampoco debe sombrear el Array global. Use un nombre de variable diferente y use el mismo nombre en todas partes en su función function binary_search(arr, key) { const middleIndex = Math.floor(arr.length / 2) const middleValue = arr[middleIndex] if (middleValue === key) return true if (arr.length <= 1) return false; if (middleValue < key) { return binary_search(arr.slice(middleIndex), key) } else if (middleValue > key) { return binary_search(arr.slice(0, middleIndex), key) } return false } console.log(binary_search(['bird', 'cat', 'dog', 'fish'], 'dog'));