Languages
[Edit]
EN

JavaScript - binary search algorithm example

14 points
Created by:
Aleena
694

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

1. Overview

Edit

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

Edit

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

Edit

4. Custom recursive implementation example

Edit
1
Donate to Dirask
Our content is created by volunteers - like Wikipedia. If you think, the things we do are good, donate us. Thanks!
Join to our subscribers to be up to date with content, news and offers.
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