基于类似二叉搜索树的算法过滤数组

Question

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

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

这个arr的长度是100,000，所以要求根据二叉搜索树过滤这个数组（由于性能方面的考虑）。但我不明白怎么办？因为二叉搜索树 return 是一个精确值，但我想 return 包括 2018 年在内的所有值，例如。
有什么线索可以实现吗？

Answer 1

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

The splice() method adds/removes items to/from an array, and returns the removed item(s).

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

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

基于类似二叉搜索树的算法过滤数组

Fiter an array based on a Binary Search Tree-like algorithm

javascript

binary-search-tree