How to find all elements in array included by range efficiently?

I have a big array of date elements, array is already sorted.

[2020.12.31, 2020.12.31, 2021.01.03, 2021.01.04, 2021.01.04, 2021.02.16, 2021.06.16] etc.

And there is some range: [2021.01.03, 2021.05.15]

I need to find all elements which are included by this range: [2021.01.03, 2021.01.04, 2021.01.04, 2021.02.16]

I coded one solution, but it is not efficient for big array. I think this can be solved by using binary search, but I don’t have idea how to.

My code:

       let i = 0,
        j = eventsId.length - 1,
        startIndex,
        endIndex
      while (!startIndex && !endIndex && i < j) {
        if (!startIndex) {
          if (
            new Date(events[eventsId[i]].startDate) >= new Date(interval.start)
          )
            startIndex = i
          else i++
        }
        if (!endIndex) {
          if (new Date(events[eventsId[j]].startDate) <= new Date(interval.end))
            endIndex = j
          else j--
        }
      }
      if (startIndex && endIndex) {
        return eventsId.slice(startIndex, endIndex + 1)
      }

1 thought on “How to find all elements in array included by range efficiently?”

  1. You could treat the date strings as string and compare directly with the range values without converting to Date objects.

    const
        data = ['2020.12.31', '2020.12.31', '2021.01.03', '2021.01.04', '2021.01.04', '2021.02.16', '2021.06.16'],
        range = ['2021.01.03', '2021.05.15'],
        result = data.filter(d => d >= range[0] && d <= range[1]);
    
    console.log(result);
    Reply

Leave a Comment