Question 256551 in Javascript Question posted in
A very good W3school tutorial can be found here.

How can I debug this Javascript code for binary search

This code is to implement binary search. However, it did not work and return undefined. I don’t know why this went wrong, please help me!

function binarySearch(arr, key) {
  let low = 0;
  let high = arr.length - 1;
  let mid
  while (low <= high) {
    mid = Math.floor((high + low) / 2);
    if (arr[mid] == key) {
      return mid;
    } else if (arr[mid] < key) {
      high = mid - 1;
    } else if (arr[mid] > key) {
      low = mid + 1;
    }
  }
  // return -1
}
console.log(binarySearch([2, 3, 4, 10, 40], 10));
Tags:

2

Answers


  1. 0

    I see the bug, but I’m going to give you an opportunity to find it first.

    Update the code to have an additional console.log statement for each iteration of your search loop.

    while (low <= high) {
    mid = Math.floor((high + low) / 2);

    // ADD THIS LINE
    console.log("low=", low, "high=", high, "mid=", mid, "arr[mid]=", arr[mid]);

    if (arr[mid] == key) {
      return mid;
    } else if (arr[mid] < key) {
      high = mid - 1;
    } else if (arr[mid] > key) {
      low = mid + 1;
    }
  }

    You’ll quickly find the bug yourself from observing the console output when you run your program again.

    Login or Signup to reply.
  2. 0

    Add some logging at each step so you can see what it going on.

    I’m not familar with exactly what you need here, but I can see that there’s only one place where you return a value, which never gets hit

    function binarySearch(arr, key) {
  let low = 0;
  let high = arr.length - 1;
  let mid
  while (low <= high) {
    mid = Math.floor((high + low) / 2);
    console.log(`key=${key}, low=${low}, mid=${mid}, high=${high}`)
    if (arr[mid] == key) {
      console.log('return mid', mid)
      return mid;
    } else if (arr[mid] < key) {
      console.log(`${arr[mid]} < ${key}`)
      high = mid - 1;
    } else if (arr[mid] > key) {
      console.log(`${arr[mid]} > ${key}`)
      low = mid + 1;
    }
  }
  // return -1
}
console.log(binarySearch([2, 3, 4, 10, 40], 10));
    Login or Signup to reply.
Please signup or login to give your own answer.

Back To Top
Search