undefined 从函数返回

Question

我正在研究二进制搜索，这是我想到的第一件事：

 function letsGoBinary(firstArray,array,search){
    const middle = Math.floor(array.length / 2);
    if(search === array[middle]) {
       const rv = firstArray.indexOf(array[middle]);
       return rv
    }else if(search < array[middle]){
       var lowerArray = []
       for(var i = 0; i < middle; i++){
           lowerArray.push(array[i])
       }
       letsGoBinary(firstArray,lowerArray, search)
    }else if(search > array[middle]){
       var forwardArray = []
       for(var i = middle + 1; i < array.length; i++){
           forwardArray.push(array[i]);
       }
       letsGoBinary(firstArray,forwardArray,search)
    }else {
       return -1
    } 
 }

console.log(letsGoBinary([1,4,7,14,16],[1,4,7,14,16], 4))

如果我在第一个 if 语句 (search === array[middle]) 中添加 console.log() 并记录 rv 它会记录准确的值，这会起作用，如果我记录 not found 在 else 语句中，它记录但在记录时 letsGoBinary 它的值未定义。我该如何解决？

Answer 1

在进行递归调用的情况下，您需要return结果。

return letsGoBinary(firstArray,lowerArray, search);

Answer 2

除了你的问题，请检查 slice 方法是如何工作的，循环不是获取数组的一部分所必需的

另外这段代码有点无意义，如果你使用

const rv = firstArray.indexOf(array[middle])

那为什么一开始不使用

const rv = firstArray.indexOf(search)

这行代码让你所有的二进制搜索变得毫无意义，因为一个一个地搜索元素

有很简单的解决方法

function letsGoBinary(array, search){
    let start = 0
    let end = array.length - 1

    while (start <= end) {
      const middle = Math.floor((start + end) / 2)   
      if(search === array[middle]) {
         return middle
      } else if (search < array[middle]) {
         end = middle - 1   
      } else {
         start = middle + 1
      }
    }

   return -1
 }

Answer 3

处理递归函数时，您应该了解基本情况，然后当您想执行递归调用时，您不仅要再次调用该函数，而且还应该 return 将函数作为响应。例如，如果搜索编号出现在 lowerArray 中，则意味着您应该 return letsGoBinary(firstArray,lowerArray, search) 作为答案。

我更新了你的代码，就是这样： 注意：看第11行和第17行

function letsGoBinary(firstArray,array,search){
            const middle = Math.floor(array.length / 2);
            if(search === array[middle]) {
                const rv = firstArray.indexOf(array[middle]);
                return rv
            }else if(search < array[middle]){
                var lowerArray = []
                for(var i = 0; i < middle; i++){
                    lowerArray.push(array[i])
                }
                return letsGoBinary(firstArray,lowerArray, search)
            }else if(search > array[middle]){
                var forwardArray = []
                for(var i = middle + 1; i < array.length; i++){
                    forwardArray.push(array[i]);
                }
                return letsGoBinary(firstArray,forwardArray,search)
            }else {
                return -1
            }
        }

        console.log(letsGoBinary([1,4,7,14,16],[1,4,7,14,16], 4))

Answer 4

这是因为当 search === array[middle] 第一次执行后，它完全是从 letsGoBinary 函数 returning，因此你必须添加另一个 return 语句，拜托找到下面的代码片段：

function letsGoBinary(firstArray,array,search){
const middle = Math.floor(array.length / 2);
if(search === array[middle]) {
   const rv = firstArray.indexOf(array[middle]);
   return rv
}else if(search < array[middle]){
   var lowerArray = []
   for(var i = 0; i < middle; i++){
       lowerArray.push(array[i])
   }
   return letsGoBinary(firstArray,lowerArray, search)
}else if(search > array[middle]){
   var forwardArray = []
   for(var i = middle + 1; i < array.length; i++){
       forwardArray.push(array[i]);
       }
       return letsGoBinary(firstArray,forwardArray,search)
    }else {
       return -1
    } 
 }

console.log(letsGoBinary([1,4,7,14,16],[1,4,7,14,16], 4))

Answer 5

Dmitry Reutov 的回答很棒。如果您更喜欢递归版本，这是一种类似的方法，但使用递归而不是 while 循环：

const letsGoBinary = (
  sortedArray, 
  value, 
  start = 0, 
  end = sortedArray .length - 1, 
  middle = Math.floor ((end + start) / 2)
) =>
  start > end
    ? -1
  : sortedArray [middle] == value
    ? middle
  : sortedArray [middle] < value
    ? letsGoBinary (sortedArray, value, middle + 1, end)
  : letsGoBinary (sortedArray, value, start, middle - 1)

console .log (
  letsGoBinary ([1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233], 34)
)

这两种解决方案都只使用一个数组，依靠 start、end 和 middle 索引来跟踪当前搜索位置。

此版本在第一次调用时默认 start 和 end，然后在后续搜索中传递它们。 middle 在每次调用时计算为 start 和 end 之间最接近的整数中点。

对于这个例子，第一次调用使用 start 和 end 的 0 和 12 使得 middle 6，并且我们正在测试的值是 sortedArray[6]，即 13。这小于34的搜索值，所以我们用7和12再次调用，这使得middle变为9和测试值55。那大于34所以我们调用7和8，7的middle，测试值21。那个小于我们的值，我们又用 start 和 end 都调用了一次 8，这给了我们一个 middle of 8 和一个34 的测试值。由于这等于我们的价值，我们 return 8。如果我们错过了——也许我们正在搜索 35——那么我们将再次调用 9 的 start 和 8 的 end，并且会 return -1，因为 start > end。或者，如果我们一直在搜索 33，我们将得到 8 的 start 和 7 的 end，结果相同 -1 .

undefined 从函数返回

undefined is returned from function

javascript

recursion

function

binary-search