如何在已排序数组中查找指定日期的前序元素及去重查询

嘿，这个场景我之前做项目的时候碰到过，刚好可以给你分享两种需求的解决方案，毕竟数组是已排序的，咱们可以利用这个特性来高效处理：

因为数组已经按日期升序排列了，咱们不用傻乎乎遍历整个数组，核心思路是找到最后一个比目标日期小的元素——这就是离目标最近的左侧元素。

这里要注意，直接用字符串比较日期可能会有坑（比如特殊格式的日期字符串比较逻辑出错），所以最好转成Date对象来做比较更稳妥。

方法1：简单遍历（易懂，适合小数组） #

var arr = ["10/27/2017","11/5/2017","11/5/2017","11/10/2017","11/10/2017","12/12/2017"];
var userDate = "11/10/2017";

const targetDate = new Date(userDate);
let closestPrev = null;

for (const dateStr of arr) {
  const currentDate = new Date(dateStr);
  if (currentDate < targetDate) {
    closestPrev = dateStr;
  } else {
    // 数组已排序，后面的日期只会更大，直接跳出循环
    break;
  }
}

console.log(closestPrev); // 输出 "11/5/2017"

方法2：二分查找（高效，适合大数据组） #

如果数组元素特别多，二分查找能把时间复杂度降到O(log n)，比遍历的O(n)快很多：

function findClosestPrev(sortedArr, targetStr) {
  const target = new Date(targetStr);
  let left = 0;
  let right = sortedArr.length - 1;
  let result = null;

  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    const currentDate = new Date(sortedArr[mid]);

    if (currentDate < target) {
      // 找到一个候选，继续往右找更接近目标的元素
      result = sortedArr[mid];
      left = mid + 1;
    } else {
      // 当前日期大于等于目标，往左找
      right = mid - 1;
    }
  }

  return result;
}

var arr = ["10/27/2017","11/5/2017","11/5/2017","11/10/2017","11/10/2017","12/12/2017"];
var userDate = "11/10/2017";
console.log(findClosestPrev(arr, userDate)); // 输出 "11/5/2017"

这个需求的核心是先拿到所有比目标日期小的不重复日期，然后按需获取更早的元素。有两种思路：

方法1：先去重再操作（直观方便） #

因为原数组是排序好的，去重非常简单，直接用Set就能搞定（或者手动遍历去重兼容旧环境），然后在去重后的数组里找目标的位置，往前取元素即可：

var arr = ["10/27/2017","11/5/2017","11/5/2017","11/10/2017","11/10/2017","12/12/2017"];
var userDate = "11/10/2017";

// 去重并保持排序顺序
const uniqueDates = [...new Set(arr)];
// 兼容旧环境的手动去重方式
// const uniqueDates = arr.reduce((acc, curr) => {
//   if (acc[acc.length - 1] !== curr) acc.push(curr);
//   return acc;
// }, []);

// 找到目标日期在去重数组中的索引
const targetIdx = uniqueDates.indexOf(userDate);

// 获取第一个不重复的前序元素
const firstUniquePrev = targetIdx > 0 ? uniqueDates[targetIdx - 1] : null;
// 获取更早的下一个不重复元素
const secondUniquePrev = targetIdx > 1 ? uniqueDates[targetIdx - 2] : null;

console.log(firstUniquePrev); // "11/5/2017"
console.log(secondUniquePrev); // "10/27/2017"

方法2：动态查找下一个更早的不重复元素（无需预先去重） #

如果不想提前生成去重数组，可以写一个函数，以上一次找到的元素为基准，继续往前找比它小的第一个不重复元素：

function findNextEarlierUnique(sortedArr, lastFoundStr) {
  const lastFoundDate = new Date(lastFoundStr);
  let result = null;
  
  // 从后往前找第一个比lastFoundStr小的不重复元素
  for (let i = sortedArr.length - 1; i >= 0; i--) {
    const currentDate = new Date(sortedArr[i]);
    if (currentDate < lastFoundDate) {
      if (sortedArr[i] !== result) {
        result = sortedArr[i];
        break; // 找到第一个就跳出，因为数组排序，这就是最近的更早元素
      }
    }
  }
  return result;
}

var arr = ["10/27/2017","11/5/2017","11/5/2017","11/10/2017","11/10/2017","12/12/2017"];
var userDate = "11/10/2017";

// 先找到第一个最近的前序元素
const firstPrev = findClosestPrev(arr, userDate);
// 找更早的不重复元素
const secondPrev = findNextEarlierUnique(arr, firstPrev);

console.log(firstPrev); // "11/5/2017"
console.log(secondPrev); // "10/27/2017"

边界情况提醒 #

• 如果目标日期是数组的第一个元素，或者数组中所有元素都等于目标日期，这两种情况都返回null，记得做判断处理哦～

内容的提问来源于stack exchange，提问作者jc1234