How to make binary search work with strings?

Question

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?

ascii sort by default ['cat', 'dog', 'bird', 'fish'].sort() — Mickael B.
– Mickael B., Commented May 30, 2022 at 14:00
Binary search works with keys of any type. The reason is elsewhere. — user1196549
– user1196549, Commented May 30, 2022 at 15:08

CertainPerformance · Accepted Answer · 2022-05-30 14:04:51Z

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

Collectives™ on Stack Overflow

How to make binary search work with strings?

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related