Calculating a midpoint with left + (right - left) / 2 returns a decimal (.5) on even length arrays. What good is that?

Question

So I must be misunderstanding something basic, but I've looked around and can't find the answer to it.

I've looked at a thread about calculating the midpoint of an array during a binary search here -

Calculating mid in binary search but it hasn't helped.

My problem is that many algorithms I've seen make use of this: midpoint = left + ((right - left) / 2).

I've had it work for me plenty of times in the past, but right now I am not understanding something.

Below is the code I am trying to execute - the first console.log of the midpoint logs 6.5.

I'm not going to find anything at index arr[6.5].

Do I have something wrong in my code,

or am I not understanding something?

let arr = ['w','x','y','z','a','b','d','e','f','g','h','i','j','k']

function rotationPoint(arr){

  let ceiling = arr.length -1
  let floor = 0
  
  while(floor < ceiling){
    
    let midpoint = floor + ((ceiling - floor) / 2)
    console.log(midpoint)

    if(arr[floor] > arr[midpoint]){
      //we know the value is in the first half
      ceiling = midpoint
    }else{
      floor = midpoint
    }
    
        if(arr[floor + 1] === arr[ceiling]){
      return ceiling
    }
  }
  

  }
  

}

console.log(rotationPoint(arr))

Answer 1

The algorithms you've seen were probably working with left and right as integral types (int, long, etc.). With integral types, 7 / 2 is 3 (3.5 with the fractional part truncated). JavaScript's numbers are floating point, not integral, so you use Math.floor (or in modern environments, Math.trunc¹) in that situation:

midpoint = Math.floor(left + ((right - left) / 2));

That way, you get a whole number.

If this is for indexes in an array, you could use bitshifting instead as in Nina's answer.

(You could also use Math.round, which will round rather than flooring, but mostly these algorithms re defined in terms of integral math...)

---

¹ The difference between floor and trunc is that floor always rounds down numerically, meaning Math.floor(-0.5) is -1. trunc just chopps off the fractional portion, so Math.trunc(-0.5) is 0 (okay, technically it's -0, but that's a whole other topic...).