This binary search works with numbers, but not working with stings
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
}
If I give it numbers, it works:
console.log(binary_search([5,7,12,16,36,39,42,56,71], 36))
output: true
But not with strings:
console.log(binary_search(['cat', 'dog', 'bird', 'fish'], 'dog'))
result : flase
I understand the array must be presorted for this to work, but how to do this with strings?
Just as you say
I understand the array must be presorted for this to work
The array of strings you're passing in is not sorted, so binary search won't be possible. If you sort it first
['bird', 'cat', 'dog', 'fish']
then your current approach will already work, mostly, because === compares strings properly, and < and > lexiographically compares strings too (it works both for numbers and strings), with some caveats:
slice to extract a segment of an array, not splice, which will remove elements from the array (a mutation!) and return an array of those returned elements (not very intuitive)numberArray variable in scope, and you also shouldn't shadow the global Array. Use a different variable name, and use the same name everywhere in your functionfunction 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'));