1

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))
Louis Sankey
  • 481
  • 8
  • 26

3 Answers3

3

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

T.J. Crowder
  • 1,031,962
  • 187
  • 1,923
  • 1,875
2

You could just add left and right and divide by two to get the midpoint.

Indices of arrays in Javascript have the same range as bitwise operations. To divide by two and getting an integer value, you could add some bitshifting.

midpoint = (floor + ceiling) >> 1;
Nina Scholz
  • 376,160
  • 25
  • 347
  • 392
0

The code in your example is running on an array of length 14, but your question asks about an odd length array. If you actually use an odd length array, your code should be fine. For an even length array you will indeed get a decimal index, so you need to choose one side or the other of your result, by rounding or truncating.

jdebr
  • 527
  • 4
  • 10