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?

CodePudding user response：

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.

CodePudding user response：

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