w3resource

JavaScript: Perform a binary search within an array

JavaScript Array: Exercise-18 with Solution

Write a JavaScript program to perform a binary search.

Note : A binary search or half-interval search algorithm finds the position of a specified input value within an array sorted by key value.


Sample array:
var items = [1, 2, 3, 4, 5, 7, 8, 9];
Expected Output:
console.log(binary_Search(items, 1)); //0
console.log(binary_Search(items, 5)); //4

Sample Solution:

JavaScript Code:

// Function to perform binary search on a sorted array
function binary_Search(items, value) {
    // Initialize variables for the first, last, and middle indices of the array
    var firstIndex  = 0,
        lastIndex   = items.length - 1,
        middleIndex = Math.floor((lastIndex + firstIndex) / 2);

    // Continue the search while the middle element is not equal to the target value
    // and the first index is less than the last index
    while (items[middleIndex] != value && firstIndex < lastIndex) {
        // Adjust the search range based on whether the target value is less or greater than the middle element
        if (value < items[middleIndex]) {
            lastIndex = middleIndex - 1;
        } else if (value > items[middleIndex]) {
            firstIndex = middleIndex + 1;
        }
        // Recalculate the middle index for the next iteration
        middleIndex = Math.floor((lastIndex + firstIndex) / 2);
    }

    // Return the index of the target value if found, otherwise return -1
    return (items[middleIndex] != value) ? -1 : middleIndex;
}

// Sorted array for testing
var items = [1, 2, 3, 4, 5, 7, 8, 9];

// Perform binary search for the target values 1 and 5
console.log(binary_Search(items, 1));   
console.log(binary_Search(items, 5));
  

Sample Output:

0
4

Flowchart:

Flowchart: JavaScript: Find duplicate values in a array

ES6 Version:

// Function to perform binary search on a sorted array
const binary_Search = (items, value) => {
    // Initialize variables for the first, last, and middle indices of the array
    let firstIndex = 0;
    let lastIndex = items.length - 1;
    let middleIndex = Math.floor((lastIndex + firstIndex) / 2);

    // Continue the search while the middle element is not equal to the target value
    // and the first index is less than the last index
    while (items[middleIndex] !== value && firstIndex < lastIndex) {
        // Adjust the search range based on whether the target value is less or greater than the middle element
        if (value < items[middleIndex]) {
            lastIndex = middleIndex - 1;
        } else if (value > items[middleIndex]) {
            firstIndex = middleIndex + 1;
        }
        // Recalculate the middle index for the next iteration
        middleIndex = Math.floor((lastIndex + firstIndex) / 2);
    }

    // Return the index of the target value if found, otherwise return -1
    return (items[middleIndex] !== value) ? -1 : middleIndex;
};

// Sorted array for testing
const items = [1, 2, 3, 4, 5, 7, 8, 9];

// Perform binary search for the target values 1 and 5
console.log(binary_Search(items, 1));   
console.log(binary_Search(items, 5));

Live Demo:

See the Pen JavaScript - Perform a binary search within an array - array-ex- 18 by w3resource (@w3resource) on CodePen.


Improve this sample solution and post your code through Disqus

Previous: Write a JavaScript program to shuffle an array.
Next: write a JavaScript program to compute the sum of each individual index value from the given arrays.

What is the difficulty level of this exercise?

Test your Programming skills with w3resource's quiz.



Follow us on Facebook and Twitter for latest update.