Languages
[Edit]
EN

JavaScript - binary search algorithm example

14 points
Created by:
Aleena
364

In this short article, we would like to show the main idea of the binary search algorithm providing example implementation in JavaScript.

1. Overview

Binary search is a fast search algorithm with run-time complexity O(log n). This algorithm requires working on sorted data with random access to each element.

2. Description

The main idea of the binary search algorithm is to:

  1. find middle point index in actual range with the formula: 
    var point = Math.ceil((index + limit) / 2);
    Notes: 
    • actual¬†range¬†has been marked with a blue dashed¬†border¬†on the below image,
    • middle point index has been marked with a¬†black arrow¬†on the below image,
    • in the beginning, the actual¬†range contains all array elements (index=0, limit=array.length-1),
    • the middle point index¬†is used to split the searching problem into 2 smaller ranges¬†- only if it is necessary for the next steps,
  2. if the middle point value is equal to the expected value, the algorithm returns the middle point index,
    Notes:
    • expected value¬†has been marked with a yellow rounded rectangle¬†on the below image,
  3. if the middle point value is not equal to the expected value, the range is split into left or right ranges with an excluded middle point, a new range that is likely to contain the expected value is selected as an actual range and we go back to 1. point (we work all-time on sorted data).
    Notes:
    • if the expected value¬†is smaller than the middle point value we select left range,
    • if the expected value¬†is bigger than the middle point value we select right range,

Algorithm iterations:

The binary search algorithm in JavaScript
The binary search algorithm in JavaScript

3. Custom iterative implementation example

// ONLINE-RUNNER:browser;

function searchIndex(array, value) {
	var index = 0;
  	var limit = array.length - 1;
  	while (index <= limit) {
        var point = Math.ceil((index + limit) / 2);
        var entry = array[point];
        if (value > entry) {
            index = point + 1;
            continue;
        }
        if (value < entry) {
            limit = point - 1;
            continue;
        }
        return point; // value == entry
    }
  	return -1;
}


// Usage example:

// for this implementation array must be sorted from smallest to biggest!
var array = [ 4, 5, 7, 11, 12, 15, 15, 21, 40, 45 ];
var index = searchIndex(array, 11); // we want to find index for 11

console.log(index);  // 3

4. Custom recursive implementation example

// ONLINE-RUNNER:browser;

function searchIndex(array, value) {
    function split(index, limit) {
        if (index > limit) {
            return -1;
        }
        var point = Math.ceil((limit + index) / 2);
        var entry = array[point];
        if (value < entry) {
            return split(index, point - 1);
        }
        if (value > entry) {
            return split(point + 1, limit);
        }
        return point; // value == entry
    }
  	return split(0, array.length - 1);
}


// Usage example:

// for this implementation array must be sorted from smallest to biggest!
var array = [ 4, 5, 7, 11, 12, 15, 15, 21, 40, 45 ];
var index = searchIndex(array, 11); // we want to find index for 11

console.log(index);  // 3

 

Native Advertising
ūüöÄ
Get your tech brand or product in front of software developers.
For more information Contact us
Dirask - we help you to
solve coding problems.
Ask question.

‚̧ԳŹūüíĽ ūüôā

Join