EN
JavaScript - binary search algorithm example
11
points
1. Overview
Binary search is a fast search algorithm with run-time complexity O(log n)
. This algorithm requires to work on sorted data with random access to each element.
The main idea of the binary search algorithm is to:
- find middle point index in actual range with the formula:
var point = Math.ceil((index + limit) / 2);
Notes:- middle point index has been marked with a black arrow on the below image,
- at the beginning actual range contains all array elements (
index=0
,limit=array.length-1
),
- if the middle point value is equal to the expected value algorithm returns index,
- if the middle point value is not equal to the expected value, the range is splitted into left or right ranges with excluded middle point,
Algorithm iterations:

2. 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;
}
// 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);
console.log(index); // 3
3. 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);
}
// 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);
console.log(index); // 3