如何使二进制搜索与字符串一起工作？

Question

此二进制搜索适用于数字，但不适用于字符串

 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


}

如果我给它数字，它就会起作用：

console.log(binary_search([5,7,12,16,36,39,42,56,71], 36))
output: true

但不适用于字符串：

console.log(binary_search(['cat', 'dog', 'bird', 'fish'], 'dog'))
result : flase

我知道必须对数组进行预排序才能正常工作，但是如何对字符串进行预排序？

Answer 1

正如你所说

I understand the array must be presorted for this to work

您传入的字符串数组未排序，因此无法进行二分查找。如果先排序

['bird', 'cat', 'dog', 'fish']

那么您当前的方法已经可行，主要是，因为 === 正确比较字符串，而 < 和 > 按字典顺序比较字符串也（它适用于数字和字符串），但有一些注意事项：

使用 slice 提取数组的一部分，而不是 splice，这将从数组中删除元素（突变！）和 return 这些 returned 元素（不是很直观）
你的范围内没有 numberArray 变量，你也不应该隐藏全局 Array。使用不同的变量名，并在函数中的所有地方使用相同的名称

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

如何使二进制搜索与字符串一起工作？

How to make binary search work with strings?

javascript

algorithm