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

Question

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

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

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

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

Answer 2

您可以使用upperBound和lowerBound二分查找。

Upper Bound 给出排序数组中元素最后一次出现的索引。

const upperBound = (sortedArray, element) => {
  let lo = 0;
  let hi = sortedArray.length - 1;

  let rightMost = -1;

  while (lo <= hi) {
    const mid = ((hi - lo) >> 1) + lo;
    
    if (sortedArray[mid] === element) {
      rightMost = Math.max(rightMost, mid);
    }

    if (sortedArray[mid] >= element) {
      lo = mid + 1;
    } else {
      high = mid - 1;
    }
  }

  return rightMost;
};

对于排序数组中数字的下界或最左侧出现，您可以使用以下命令：

const lowerBound = (sortedArray, element) => {
  let lo = 0;
  let hi = sortedArray.length - 1;

  while (lo <= hi) {
    const mid = ((hi - lo) >> 1) + lo;
    if (sortedArray[mid] > element) {
      hi = mid - 1;
    } else {
      lo = mid + 1;
    }
  }

  return lo;
};