Has the binary search operation not been executed?

Question

Has the binary search operation not been executed?

My attempt to implement the binary search algorithm in my code example is not producing the expected result. I'm unsure of the cause. Can someone please explain it to me?

var array = [1, 4, 6, 8, 9, 12, 15, 17, 19, 34, 55, 78, 80];

function binarySearch (array, numberToSearch) {
var firstIndex = 0;
var lastIndex = array.length - 1;
var currentIndex;
var currentElement;

currentIndex = (lastIndex + firstIndex) / 2 | 2;
currentElement = array[currentIndex];

while (firstIndex <= lastIndex) {
    if (numberToSearch === currentElement) {
        // found
        console.log(currentIndex);
        return currentIndex;
    } else if (numberToSearch < currentElement) {
        lastIndex = currentIndex - 1;
        currentIndex = (lastIndex + firstIndex) / 2 | 2;
        currentElement = array[currentIndex];
    } else if (numberToSearch > currentElement) {
        firstIndex = currentIndex + 1;
        currentIndex = (lastIndex + firstIndex) / 2 | 2;
        currentElement = array[currentIndex];
    }
}
 return -1;
}
binarySearch(array, 12);

When running the function with the value of 12, I should be getting a result of 5, but nothing is happening.

javascript arrays algorithm search data-structures

Answer 1

Answer №1

What issue is present in the code:

The correct syntax should be

var currentIndex = (lastIndex + firstIndex) / 2 | 0;

(instead of | 2);

currentIndex and currentElement need to be recalculated during each iteration within the loop.

Therefore, here is the revised version of your code:

var array = [1, 4, 6, 8, 9, 12, 15, 17, 19, 34, 55, 78, 80];

function binarySearch (array, numberToSearch) {
var firstIndex = 0;
var lastIndex = array.length - 1;

while (firstIndex <= lastIndex) {
    var currentIndex = (lastIndex + firstIndex) / 2 | 0;
    var currentElement = array[currentIndex];
    if (numberToSearch === currentElement) {
        return currentIndex;
    } else if (numberToSearch < currentElement) {
        lastIndex = currentIndex - 1;
    } else if (numberToSearch > currentElement) {
        firstIndex = currentIndex + 1;
    }
}
 return -1;
}

console.log(binarySearch(array, 99)); // -1
console.log(binarySearch(array, 12)); // 5

By the way, using

var currentIndex = (lastIndex + firstIndex) / 2 | 0;

may be unfamiliar. A more common approach is

var currentIndex = Math.floor((lastIndex + firstIndex) / 2);

Answer 2

What issue is present in the code:

The correct syntax should be

var currentIndex = (lastIndex + firstIndex) / 2 | 0;

(instead of | 2);

currentIndex and currentElement need to be recalculated during each iteration within the loop.

Therefore, here is the revised version of your code:

var array = [1, 4, 6, 8, 9, 12, 15, 17, 19, 34, 55, 78, 80];

function binarySearch (array, numberToSearch) {
var firstIndex = 0;
var lastIndex = array.length - 1;

while (firstIndex <= lastIndex) {
    var currentIndex = (lastIndex + firstIndex) / 2 | 0;
    var currentElement = array[currentIndex];
    if (numberToSearch === currentElement) {
        return currentIndex;
    } else if (numberToSearch < currentElement) {
        lastIndex = currentIndex - 1;
    } else if (numberToSearch > currentElement) {
        firstIndex = currentIndex + 1;
    }
}
 return -1;
}

console.log(binarySearch(array, 99)); // -1
console.log(binarySearch(array, 12)); // 5

By the way, using

var currentIndex = (lastIndex + firstIndex) / 2 | 0;

may be unfamiliar. A more common approach is

var currentIndex = Math.floor((lastIndex + firstIndex) / 2);

Answer 3

Answer №2

Let's discuss the purpose of using the bitwise operand OR in this situation:

currentIndex = (lastIndex + firstIndex) / 2 | 2;

It seems that a correction is needed. The expression should simply be:

currentIndex = (lastIndex + firstIndex) / 2;

There appears to be an error in updating the search space. When

numberToSearch < currentElement

, indicating that the middle element (element at index currentIndex) is greater than the number being searched, the correct adjustment for the boundaries would be:

lastIndex = currentIndex - 1;

Similarly, when

numberToSearch > currentElement

, showing that the middle element (element at index currentIndex) is less than the number being searched, the proper update for the boundaries should be:

firstIndex = currentIndex + 1;

The revised and accurate code snippet is as follows:

var array = [1, 4, 6, 8, 9, 12, 15, 17, 19, 34, 55, 78, 80];

function binarySearch(array, numberToSearch) {
    var firstIndex = 0;
    var lastIndex = array.length - 1;
    var currentIndex;
    var currentElement;

    currentIndex = (lastIndex + firstIndex) / 2;
    currentElement = array[currentIndex];

    while (firstIndex <= lastIndex) {
        if (numberToSearch === currentElement) {
            // Element found
            console.log(currentIndex);
            return currentIndex;
        } else if (numberToSearch < currentElement) {
            lastIndex = currentIndex - 1;
            currentIndex = (lastIndex + firstIndex) / 2;
            currentElement = array[currentIndex];
        } else if (numberToSearch > currentElement) {
            firstIndex = currentIndex + 1;
            currentIndex = (lastIndex + firstIndex) / 2;
            currentElement = array[currentIndex];
        }
    }

    return -1;
}
binarySearch(array, 12);

Answer 4

Let's discuss the purpose of using the bitwise operand OR in this situation:

currentIndex = (lastIndex + firstIndex) / 2 | 2;

It seems that a correction is needed. The expression should simply be:

currentIndex = (lastIndex + firstIndex) / 2;

There appears to be an error in updating the search space. When

numberToSearch < currentElement

, indicating that the middle element (element at index currentIndex) is greater than the number being searched, the correct adjustment for the boundaries would be:

lastIndex = currentIndex - 1;

Similarly, when

numberToSearch > currentElement

, showing that the middle element (element at index currentIndex) is less than the number being searched, the proper update for the boundaries should be:

firstIndex = currentIndex + 1;

The revised and accurate code snippet is as follows:

var array = [1, 4, 6, 8, 9, 12, 15, 17, 19, 34, 55, 78, 80];

function binarySearch(array, numberToSearch) {
    var firstIndex = 0;
    var lastIndex = array.length - 1;
    var currentIndex;
    var currentElement;

    currentIndex = (lastIndex + firstIndex) / 2;
    currentElement = array[currentIndex];

    while (firstIndex <= lastIndex) {
        if (numberToSearch === currentElement) {
            // Element found
            console.log(currentIndex);
            return currentIndex;
        } else if (numberToSearch < currentElement) {
            lastIndex = currentIndex - 1;
            currentIndex = (lastIndex + firstIndex) / 2;
            currentElement = array[currentIndex];
        } else if (numberToSearch > currentElement) {
            firstIndex = currentIndex + 1;
            currentIndex = (lastIndex + firstIndex) / 2;
            currentElement = array[currentIndex];
        }
    }

    return -1;
}
binarySearch(array, 12);

Answer 5

Answer №3

I have made the necessary updates to your answer. You were almost there! It appeared that you mixed up the iterative binary search with the recursive solution.

Check out this CodePen Demo

var array = [1, 4, 6, 8, 9, 12, 15, 17, 19, 34, 55, 78, 80];

function binarySearch (array, numberToSearch) {
  var firstIndex = 0;
  var lastIndex = array.length - 1;
  var currentIndex;
  var currentElement;

  while (firstIndex <= lastIndex) {
    currentIndex = (lastIndex + firstIndex) / 2 | 0; //should default to zero, not Two! 
    currentElement = array[currentIndex];//These should both update every iteration so it does not infinitely loop!
    if (numberToSearch === currentElement) {
      // found
      console.log(currentIndex);
      return currentIndex;
    }else if (numberToSearch < currentElement) {
      lastIndex = currentIndex - 1; //If current is too big, move right pointer to the left
    }else if (numberToSearch > currentElement) {
      firstIndex = currentIndex + 1;//If current is too small, move left pointer to the right
    }
  }
  return -1;//When condition of while it broken and no solution has been found, return -1 to indicate it is not in the array
}
binarySearch(array, 12) //5

This approach is further optimized by not using Math.floor() as number | 0 can be faster at times.

Answer 6

I have made the necessary updates to your answer. You were almost there! It appeared that you mixed up the iterative binary search with the recursive solution.

Check out this CodePen Demo

var array = [1, 4, 6, 8, 9, 12, 15, 17, 19, 34, 55, 78, 80];

function binarySearch (array, numberToSearch) {
  var firstIndex = 0;
  var lastIndex = array.length - 1;
  var currentIndex;
  var currentElement;

  while (firstIndex <= lastIndex) {
    currentIndex = (lastIndex + firstIndex) / 2 | 0; //should default to zero, not Two! 
    currentElement = array[currentIndex];//These should both update every iteration so it does not infinitely loop!
    if (numberToSearch === currentElement) {
      // found
      console.log(currentIndex);
      return currentIndex;
    }else if (numberToSearch < currentElement) {
      lastIndex = currentIndex - 1; //If current is too big, move right pointer to the left
    }else if (numberToSearch > currentElement) {
      firstIndex = currentIndex + 1;//If current is too small, move left pointer to the right
    }
  }
  return -1;//When condition of while it broken and no solution has been found, return -1 to indicate it is not in the array
}
binarySearch(array, 12) //5

This approach is further optimized by not using Math.floor() as number | 0 can be faster at times.

Has the binary search operation not been executed?

Answer №1

Answer №2

Answer №3

Similar questions

React Native Header Icon Not Showing on the Left Side

"Why does adding a new span create space between it and the previous ones, and what can be done to prevent this from

Next.JS reported that it "Executed a greater number of hooks compared to the previous render"

Struggling to display my array data retrieved from the database on my Angular 5 page

Offering various language options on a website determined by the URL

Access the value of a variable passed from the view to the controller

The scroll feature in JavaScript is malfunctioning

"Struggling with solving an error in METEOR REACT SEARCH and DISPLAY upon user input onChange? Let

reading blocks of 2-byte integers

Make sure to validate onsubmit and submit the form using ajax - it's crucial

Tips on arranging jQuery deferred objects in order?

AngularFire Google OAuth failing to retrieve the user's email address

Unable to remove spaces in string using Jquery, except when they exist between words

Utilizing Vue.js to pass a slot to a customized Bootstrap-Vue Table component

Identifying sluggish GPU performance on a mobile device using three.js: A guide for developers

Python: Exploring Multi-Index Looping

Encountering issues with running an AngularJS application (version 1.6) in Visual Studio following the activation of script

Leveraging JavaScript to trigger onClick() functions for multiple buttons throughout a webpage

Utilize jQuery to toggle classes on multiple elements in web development

Neglecting to pass data to the controller through the onclick function