javascript - 基于类似二叉搜索树的算法拟合数组

Question

我有一个这样的日期排序数组：

let arr = ['2019-03-12', '2019-02-11', '2019-02-09', '2018-06-09', '2018-01-24', ..]

这arr是长度100,000，因此要求基于二叉搜索树过滤此数组（出于性能考虑）。但我不明白怎么做？因为二叉搜索树返回一个确切的值，但我想返回包括 2018 在内的所有值，例如。
任何线索我该如何实施？

标签： javascriptbinary-search-tree

Answer 1

正如您所提到的， abinary search将从集合中为您提供一个值。在这种情况下，您可以简单地做的是，您可以拼接从您返回的值binary search并重复，直到没有包含 2018 的元素。

splice() 方法在数组中添加/删除项目，并返回删除的项目。

当然，您需要存储返回的值。

let arr = ['2019-03-12', '2019-02-11', '2019-02-09', '2018-06-09', '2018-01-24', '2018-01-24'];

    arr.sort();
    let filteredArr = [];
    let result = 0;
    while (result !== -1) {
       result = bSearch(arr, '2018');
       if (result !== -1) {
          filteredArr.push(arr[result]);
          arr.splice(result, 1);
       }
    }
    // Your filtered array
    console.log(filteredArr)

    function bSearch(arr, x) { 
        let start=0, end=arr.length-1; 
        while (start <= end){
            let mid = Math.floor((start + end) / 2);
            // If element is present at mid, return index 
            if (arr[mid].substring(0,4) === (x)) return mid; 
            else if (arr[mid] < x)
                 start = mid + 1; 
            else
                 end = mid - 1;
        } 
        return -1; 
    }