CODEWITHSUNDEEP
javascriptalgorithm
PinPiguin
PinPiguin

Reputation: 477

How to make binary search work with strings?

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?

Upvotes: 1

Views: 795

Answers (1)

CertainPerformance
CertainPerformance

Reputation: 371193

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:

  • Use 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)
  • You do not have a 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 function

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'));

Upvotes: 4

Related Questions