2

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

AlekseyHoffman
  • 2,438
  • 1
  • 8
  • 31

2 Answers2

2

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.

Bergi
  • 630,263
  • 148
  • 957
  • 1,375
  • Thanks for the answer. So if the target is `4000` and the array is `10000` long [48, 48. 48, ..., 48] do we have to do 83 iterations: `[48] < 4000; [48 + 48] < 4000; [48 + 48 + 48] < 4000; ...` to find the index? Can't we avoid it with the binary search I described? – AlekseyHoffman Sep 16 '20 at 13:06
  • What do you mean by "83 iterations"? You need only a single iteration, but until index 83, yes. – Bergi Sep 16 '20 at 13:09
  • Hmm, yeah, I' don't know why I thought a binary search would optimize the calculations, we still have to sum all the indexes up to the target. Shouldn't be coding late at night... – AlekseyHoffman Sep 16 '20 at 13:52
  • Wait, I'm confused now, my binary search algorithm is actually valid here, I just remembered how I figured it out. Think about it. Instead of adding up all the indexes until we find the one at which `sum === target` (`1st check:` array[0]; `2nd check:` array[0] + array[1]; `3rd check:` array[0] + array[1] + array[2]; ... `83rd check:` array[0] + ... + array[82]) which will take 83 checks, instead we can do just 1 large slice check: `sum(array[0], array[5000])` and see if we NEED to do all these 83 additions... – AlekseyHoffman Sep 16 '20 at 15:21
  • Because if array is `10000` long and the target is farther than half of the array deep `target > sum(array[0], array[5000])` it means we didn't need to do all these hundreds of checks – AlekseyHoffman Sep 16 '20 at 15:25
  • There's definitely some confusion here. What is this `sum` call doing, just `array[0] + array[5000]`? Then it's wrong. If it's summing up all values between index 0 an 5000, then that's just the loop again. – Bergi Sep 16 '20 at 15:28
  • Say we have 10 elements of the same `48px` height for simplicity: [48, 48, 48, 48, 48, 48, 48, 48, 48, 48] and let's say the container is scrolled down to 385px, which means it is scrolled by 8 elements (385 / 48). If all the elements are of same height, it's easy to find, it's just 1 division, but if all elements are of different height, we cannot do that and we need to do 8 additions before we find the index: 1st: array[0]; 2nd: array[0] + array[1], etc. but if we just sum half of the array we will get 240 (48*5) and find that we didn't need to do those 8 additions cuz the target is further – AlekseyHoffman Sep 16 '20 at 15:39
  • You see what I mean? Imagine if the array is 10000 elements long instead of just 10 elements long, you see how many additions we would have to do before we find the index if it's not in the beginning. And by using the binary search we can dramatically reduce the amount of additions we need to do to find the index. We know the scroll (target) position, let's say it's 26000px down in this example, so we can just cut the array in half 24000px (48px*500) and immediately find that we didn't need to do all the additions up until the 500th index. So the algorithm works, right? – AlekseyHoffman Sep 16 '20 at 15:47
  • @AlexHoffman **Iff** all elements are of the same height, yes. As that allows you to replace the repeated addition by a simple multiplication. But if the array elements don't all have the same value (and that's the assumption of my answer), we're back to additions. – Bergi Sep 16 '20 at 15:55
  • I agree, we have to use additions if the array is dynamic, but instead of doing 541 additions to find the that we get to 26000px at index 541, instead we can use binary search and find it in under 10 operations: first we sum 50% slice of the array and get ~24000px in just a single addition, and then we sum 75% of the array and get ~36000px and then we sum half of the indexes between that 50%and 75% and get ~30000px and then we sum half of the indexes between that 50% and 62% and get ~26880px. See how close we got to the target in just 4 operations? – AlekseyHoffman Sep 16 '20 at 17:07
  • @AlexHoffman No, the problem is that there is no `sum` operation. When you say "*first we sum 50% slice of the array*", that does *mean* doing 270 addition operations. – Bergi Sep 16 '20 at 19:08
  • Ahh, man, thank you for pointing that out, you are right. I can't believe my brain turned the sum operation into an abstraction. I don't know why I was thinking about it conceptually like that. Too much programming can really break your brain for the day, unbelievable... – AlekseyHoffman Sep 16 '20 at 19:52
2

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?

Mohd Abdul Mujib
  • 13,071
  • 8
  • 64
  • 88
  • Basically, I have a container with elements of different heights (36, 48, etc) and a `scroll` event, which returns the amount of scrolled pixels from the top, so I'm trying to find the element to which the container is scrolled at – AlekseyHoffman Sep 16 '20 at 13:09
  • 1
    @AlexHoffman For that, you might want to use an [intersection observer](https://developer.mozilla.org/en-US/docs/Web/API/IntersectionObserver) anyway. But notice that you don't need to use the element's `height`s, the browser did calculate the sums for you already - you can just run a binary (or even better, interpolation) search on the [`offsetTop`](https://developer.mozilla.org/en-US/docs/Web/API/HTMLElement/offsetTop)s. – Bergi Sep 16 '20 at 13:11
  • So these elements, can they be multiple in one row? or one in each row? – Mohd Abdul Mujib Sep 16 '20 at 13:15
  • 1
    How about [this](https://stackoverflow.com/questions/487073/how-to-check-if-element-is-visible-after-scrolling)? – Mohd Abdul Mujib Sep 16 '20 at 13:15
  • 1
    @Bergi MohdAbdulMujib thanks guys, I guess it's a better idea to use the browser's layout calculations instead of doing it myself. The only problem is that the container is virtual so it always renders only ~10 elements, and the intersection obeserver wouldn't know what subset of elements is rendered. But I think I understand how to make it work now – AlekseyHoffman Sep 16 '20 at 13:31