javascript - JS 数组二分查找中的递归与无递归

标签 javascript arrays recursion binary-search

我编写了一种递归方法,用于查找数组中不重复的单个项目(而所有其他项目都是成对且彼此相邻的)。。我的问题是,这是否可以在没有递归的情况下完成(也许使用 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];

谢谢。

最佳答案

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

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];

(假设数组已排序,并且每个项目恰好出现一次或两次)。

关于javascript - JS 数组二分查找中的递归与无递归,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/39583376/

相关文章:

javascript - 联系表格 - 仅在 html 中包含的 Html 和 Javascript (tumblr)

javascript - 使用 Filereader API 加载图像并使用 JSZip 压缩它

java - JLabel 数组中的空指针异常

javascript - 嵌套 JavaScript 数组的分隔列表

c - 数组输入问题

Python networkx图复制进入递归循环并失败

javascript - D3 获取变量值

C - 递归复制文件

haskell - 为什么这是一个非详尽的搜索模式?

javascript - 使用 javascript 和正则表达式获取查询字符串