数组上 JS 二进制搜索中的递归与非递归

Question

我已经编写了一种递归方法，用于查找数组中不重复的 单个项目（而所有其他项目都是成对且相邻的）。我的问题是，这是否可以在没有递归的情况下完成（可能使用 while 循环）并且在函数内使用循环比仅使用递归更有效（就内存而言）？

当前解决方案：

function findSingularElement(arr, low, high) {
  // base cases
  if (arr.length < 3) return console.log('Invalid length of array.');
  if (low > high) return;
  if (low == high) return console.log(arr[low]);

  var mid = low + (high - low) / 2;

  if (mid % 2 === 0) {
    if (arr[mid] == arr[mid + 1]) {
      return findSingularElement(arr, mid + 2, high);
    } else {
      return findSingularElement(arr, low, mid);
    }
  } else {
    if (arr[mid] == arr[mid - 1]) {
      return findSingularElement(arr, mid + 1, high);
    } else {
      return findSingularElement(arr, low, mid - 1);
    }
  }
}

var array = [1, 1, 3, 3, 4, 5, 5, 7, 7, 8, 8];

谢谢。

Answer 1

要从函数中删除递归，只需将递归调用替换为适当的变量赋值即可：

function findSingularElement1(arr) {
    if (arr.length < 3)
        throw('Invalid length of array.');

    var low = 0, high = arr.length - 1;

    while (low < high) {

        var mid = low + (high - low) / 2;

        if (mid % 2 === 0) {
            if (arr[mid] == arr[mid + 1]) {
                low = mid + 2;
            } else {
                high = mid;
            }
        } else {
            if (arr[mid] == arr[mid - 1]) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
    }
    return low == high ? arr[low] : null;
}

也就是说，您的整个方法似乎过于复杂，您可以通过简单的循环轻松找到未配对的项目：

for (var i = 0; i < array.length; i += 2)
    if (array[i] != array[i + 1])
        return array[i];

（假设数组已排序，且每一项恰好出现一次或两次）。

Answer 2

我的回答，只是玩得开心！

var numberArray = [1, 3, 6, 8, 9, 11, 16, 27, 33, 37, 56, 78];

function recursiveBinary(sortedArray, target, start, end) {
    var start = start || 0;
  var end = end || sortedArray.length;
    var middle = Math.floor((start + end) / 2);

    if (start > end) {
    return -1;
  }

  if (target === sortedArray[middle]) {
    return sortedArray[middle];
  } else if (target < sortedArray[middle]) {
    return recursiveBinary(sortedArray, target, start, middle - 1);
  } else if (target > sortedArray[middle]) {
    return recursiveBinary(sortedArray, target, middle + 1, end);
  }

}

var sum = recursiveBinary(numberArray, 9);

Answer 3

任何用递归完成的事情，都可以用循环代替。递归可以做而循环不能做的唯一一件事就是使代码简单明了。通过用循环替换基本条件，可以在二进制搜索中删除递归。

 function binarySearch(arr,ele){
  let low = 0;
  let high = arr.length-1;
  while(low<=high){
   let mid = Math.floor((low+high)/2) 
   if(arr[mid]==ele) 
     return true;
   else if(arr[mid]>ele)
     high = mid-1;
   else
     low = mid+1;
    }
  return false;
 }

数组上 JS 二进制搜索中的递归与非递归

Recursion vs No Recursion in JS Binary Search on Array

javascript

arrays

recursion

binary-search