JavaScript: how do I use binary search to find numbers in a sorted array within a given range

Question

I am trying to write a function to return a subset of a sorted input array where all the numbers are within the input range. For example:


getNumsWithin([1,2,3,5,6,7], [3.3, 6.7]) // [5, 6]
getNumsWithin([1,2,3,5,6,7], [6, 7]) // [6, 7]
getNumsWithin([1,2,3,5,6,7], [8, 10]) // []

Given the input array is always sorted, I assume I can use binary search to find a start index and an end index and just slice the original array with them.

Here is my attempt:

function findStartIdx(sortedArray, target) {
  let start = 0,
    end = sortedArray.length - 1

  while (start < end) {
    const mid = Math.floor((start + end) / 2)
    if (sortedArray[mid] < target) start = mid
    else end = mid - 1
  }

  return start + 1
}

function findEndIdx(sortedArray, target) {
  let start = 0,
    end = sortedArray.length - 1

  while (start < end) {
    const mid = Math.floor((start + end) / 2)
    if (sortedArray[mid] < target) start = mid + 1
    else end = mid
  }

  return end + 1
}

function getNumsWithin(array, range) {
  const startIndex = findStartIdx(array, range[0])
  const endIndex = findEndIdx(array, range[1])

  return array.slice(startIndex, endIndex + 1)
}

But the binary search would end up being a endless loop if the target happens to the last num in the array. Also I wonder if we can just search it once instead of twice to find both the start and the

I am struggling to write such a function. can someone help me out?

trincot · Accepted Answer · 2022-09-28 21:38:56Z

1

Your idea is fine, but the binary search functions need some changes:

The while condition should allow start and end to be equal.
The comparison of target in the second version should be different so that equal values are included in the final range.

Here is a correction of both:

function findStartIdx(sortedArray, target) {
  let start = 0,
    end = sortedArray.length - 1

  while (start <= end) {
    const mid = Math.floor((start + end) / 2)
    if (sortedArray[mid] < target) start = mid + 1
    else end = mid - 1
  }

  return start
}

function findEndIdx(sortedArray, target) {
  let start = 0,
    end = sortedArray.length - 1

  while (start <= end) {
    const mid = Math.floor((start + end) / 2)
    if (sortedArray[mid] <= target) start = mid + 1
    else end = mid - 1
  }

  return end
}

On a final note: in terms of time complexity it would be fine to only perform one binary search, and then continue with a linear search through the array. This is because taking the slice represents the same time complexity as searching the end of the slice with a linear search: both are O(slicesize). But given that in JavaScript the slice method is fast compared to a more "manual" linear search with an explicit loop, you'll get better results with these two binary searches.

answered Sep 28, 2022 at 21:38

trincot

357k38 gold badges282 silver badges338 bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

Joji Over a year ago

thanks! could you maybe add the code snippet that incorporates the optimization you mentioned at the end?

trincot Over a year ago

I think you misunderstand. Your algorithm idea with 2 binary searches is fine. There is no optimisation. I merely pointed to an alternative that has the same time complexity, but for large arrays would perform worse because of the tools that JavaScript offers.

Joji Over a year ago

got it thanks! is there a way to find the start and end index using one binary search pass instead of two separate searches?

trincot Over a year ago

No, ... well, you can combine them in one function, but essentially you'll still do 2 binary searches. Nothing to worry about. When you do one binary search, it doesn't increase the time complexity to do a second one.

IT goldman · Accepted Answer · 2022-09-28 21:49:21Z

Just need to make sure findStartIdx works, then the rest is easy. So instead of looking for exact match as in normal binary search, we look for a match between two numbers at index mid and mid + 1.

Edge cases: haven't tested if same numbers appear multiple times. Need to fix findEndIdx a bit.

var arr = [1, 2, 3, 5, 6, 7]
var start = 0
var end = arr.length - 1;

console.log(getNumsWithin(arr, [3.3, 6.7]))
console.log(getNumsWithin(arr, [6, 7]))
console.log(getNumsWithin(arr, [8, 10]))

function findStartIdx(sortedArray, x, start, end) {
  if (start > end) return -1;
  let mid = Math.floor((start + end) / 2);
  if (arr[mid] <= x) {
    if (mid === arr.length - 1) {
      return mid;
    }
    if (arr[mid + 1] >= x) return mid;
    return findStartIdx(sortedArray, x, mid + 1, end);
  } else {
    return findStartIdx(sortedArray, x, start, mid - 1);
  }
}

// hehe
function findEndIdx(sortedArray, x, start, end) {
  var result = findStartIdx(sortedArray, x, start, end) + 1
  if (result == sortedArray.length) return -1;
  return result;
}


function getNumsWithin(array, range) {
  const startIndex = findStartIdx(array, range[0], start, end)
  const endIndex = findEndIdx(array, range[1], start, end)
  if (startIndex == -1 || endIndex == -1) {
    return [];
  }
  return array.slice(startIndex, endIndex + 1)
}

Collectives™ on Stack Overflow

JavaScript: how do I use binary search to find numbers in a sorted array within a given range

2 Answers 2

4 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

4 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related