How to efficiently find the index of a number in an array at which all the previous indexes add up to a given integer N?

user_12125881 0
Viewed 90

UPDATE: I realized the question is invalid. Ignore it. I made a mistake in the for loop, it actually takes only ~1 ms to sum all the indexes, not half a second, that lead me to the assumption it can be optimized with binary search, which does not apply here.

Let's say we have:

  • an integer target = 85
  • an array of integers array = [36, 48, 48, 36, 48, 48, 48, 48, 48, 48]

How would we efficiently find the index at which sum(array[0], array[N]) > target ? In this example, the index would be 2 because the sum of indexes exceeds the target at index 2.

Basically, I have a virtual container of elements (it renders only a small subset of elements at all times) all of which have different heights (36, 48, etc) and a scroll event that returns the amount of scrolled pixels (target), so I'm trying to find the element to which the container is scrolled to, in this example the container is scroll 85px down, which means it scrolled pass the element 2.

Example:

let target = 85
let array = [36, 48, 48, 36, 48, 48, 48, 48, 48, 48]

// Finding the element with a bruteforce method:
array[0] > target // false
array[0] + array[1] > target // false
array[0] + array[1] + array[2] > target // true
return 2

For some reason trying to sum all the indexes until we find the target value using a for loop takes half a second per 1000 values.

I'm not sure if there's a well known algorithm for this already, but I figured I have to use a custom derivative form of a binary search to find the index in just a few iterations, for example:

Divide the array in half
Sum all the indexes in the left half
If the target < sum, it means the target is in the left half, so divide it again
If the target > sum, extend the search to the right half
Repeat recursively

I've partially created this recursive algorithm but I'm having difficulties figuring out how to properly handle the condition when the target is in the "right half" of the array, i.e. when target > halfSliceSum:

let target = 85
let array = [36, 48, 48, 36, 48, 48, 48, 48, 48, 48]
console.log(getElementIndexAtTargetPosition(array, target))

function getElementIndexAtTargetPosition(array, target) {
  // TESTS (expected results):
  // ([36, 48, 48, 36, 48, 48, 48, 48, 48, 48], 35) => return 0
  // ([36, 48, 48, 36, 48, 48, 48, 48, 48, 48], 36) => return 0
  // ([36, 48, 48, 36, 48, 48, 48, 48, 48, 48], 37) => return 1
  // ([36, 48, 48, 36, 48, 48, 48, 48, 48, 48], 84) => return 1
  // ([36, 48, 48, 36, 48, 48, 48, 48, 48, 48], 85) => return 2
  // ([36, 48, 48, 36, 48, 48, 48, 48, 48, 48], 456) => return 8

  let halfIndex = Math.round(array.length / 2)
  let halfSlice = array.slice(0, halfIndex)
  let halfSliceSum = halfSlice.reduce((a, b) => a + b, 0)
  if (array.length === 1) {
    return 0
  }
  if (target === halfSliceSum) {
    return halfIndex
  }
  else if (target < halfSliceSum) {
    return getElementIndexAtTargetPosition(halfSlice, target)
  }
  else if (target > halfSliceSum) {
    // Increase search slice by Math.round(halfIndex * 1.5)?
    // ...
  }
}

The target is always within the array, i.e. target <= sum(array[0], array[lastIndex])

javascript
2 Answers

You must sum up all the individual values until you reach the threshold, there's no other way of doing it when you are just given the array.

However, if you have to do this multiple times it can help to transform the array into one of increasing sums, on which you then can run the binary search (assuming there are no negative summands so it actually is an increasing sequence). You might even drop the original array, as you can still access its values by computing differences.

user_10485720

I agree with the answer provided by @bergi. Specially if the array is not in a given sequence or pattern.

The thing that you are proposing is a false sense of optimization. Though it may look like it, You are not doing a "binary" search. You are still doing the "unoptimized" work of adding the full array albeit in two halves. And in the best case this "binary" approach will end up needing one more iteration than the "linear" approach.

As mentioned already, The most effecient approach is to just keep adding till you reach the condition.

On a side note, this looks like a XY problem, what exactly are you trying to achieve in the first palce?

user_8071040
Related