Binary Search Algorithmn - infinity loop

Question

I have a problem with my Binary Search algorithm. I'm trying to implement it in javascript but still it get a infinity loop. Here's my code:

var a = [1, 4, 5, 8, 11, 15]

function binarySearch(arr, item){
  let low = 0
  let high = arr.length - 1

  while(low <= high) {
    var m = (low + high)/2 | 0
    if(arr[m] == item){
        console.log("Item found in index: " + m)
      return false;
    } else {
            if(a[m] > item){
            console.log("Too high")
          h = m - 1
        } else {
            console.log("Too low")
          l = m + 1
        }
    }
  }
  console.log("Item not found")
  return false;
}

binarySearch(a, 1)

You should Math.floor or Math.ceil the value (low + high) / 2 before assigning it to m. And you should use the same variables either low and high or l and h, not both. — ibrahim mahrir
– ibrahim mahrir, Commented Dec 11, 2017 at 15:09
while(low <= high) You don't actually modify either of those variables inside the loop so if the condition starts as true it can never become false. — takendarkk
– takendarkk, Commented Dec 11, 2017 at 15:09
Ok, thanks i didn't noticed that i use "l" and "h" instead of "low" and "high". Now it's working, thanks a lot. Btw. Math.floor is working the same as | 0 — sh3ev
– sh3ev, Commented Dec 11, 2017 at 15:14
@sh3ev, no, bitwise OR converts a number to first to 32 bit and then back to 64 bit float, whereas Math.floor keeps the number in 64bit float. — Nina Scholz
– Nina Scholz, Commented Dec 11, 2017 at 15:43

Tam-Thanh Le · Accepted Answer · 2020-05-16 15:02:18Z

2

Try this (editted something wrong from your code):

var a = [1, 4, 5, 8, 11, 15]

function binarySearch(arr, item) {
    var low = 0
    var high = arr.length - 1

    while (low <= high) {
        let m = low + (high - low ) / 2
        if (arr[m] == item) {
            console.log("Item found in index: " + m)
            return false;
        }
        if(a[m] > item) {
            console.log("Too high")
            hight = m - 1
        } else {
            console.log("Too low")
            low = m + 1
        }
    }
    console.log("Item not found")
    return false;
}

binarySearch(a, 1)

edited May 16, 2020 at 15:02

answered May 16, 2020 at 14:57

Tam-Thanh Le

3331 silver badge11 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Binary Search Algorithmn - infinity loop

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related