JavaScript: выполнить бинарный поиск в массиве

Последнее обновление 9 февраля 2019 08:36:10 (UTC / GMT +8 часов)

script1adsense2code

script1adsense3code

Массив JavaScript: упражнение 18 с решением

Напишите программу на JavaScript для выполнения бинарного поиска.

Примечание. Алгоритм бинарного или полуинтервального поиска находит положение указанного входного значения в массиве, отсортированном по значению ключа.

Образец массива:
var items = [1, 2, 3, 4, 5, 7, 8, 9];
Ожидаемый результат:
console.log (binary_Search (items, 1)); // 0
console.log (binary_Search (items, 5)); // 4

Пример решения:

HTML-код:

<!DOCTYPE html>
<html>
<head>
<meta charset="utf-8">
<title>Binary Search</title>
</head>
<body>
</body>
</html>

Код JavaScript:

function binary_Search(items, value){
    var firstIndex  = 0,
        lastIndex   = items.length - 1,
        middleIndex = Math.floor((lastIndex + firstIndex)/2);
    while(items[middleIndex] != value && firstIndex < lastIndex)
    {
       if (value < items[middleIndex])
        {
            lastIndex = middleIndex - 1;
        } 
      else if (value > items[middleIndex])
        {
            firstIndex = middleIndex + 1;
        }
        middleIndex = Math.floor((lastIndex + firstIndex)/2);
    }
 return (items[middleIndex] != value) ? -1 : middleIndex;
}
var items = [1, 2, 3, 4, 5, 7, 8, 9];
console.log(binary_Search(items, 1));   
console.log(binary_Search(items, 5));

Пример вывода:

0
4

Блок - схема:

Версия ES6:

function binary_Search(items, value){
    let firstIndex  = 0;
    let lastIndex   = items.length - 1;
    let middleIndex = Math.floor((lastIndex + firstIndex)/2);
    while(items[middleIndex] != value && firstIndex < lastIndex)
    {
       if (value < items[middleIndex])
        {
            lastIndex = middleIndex - 1;
        } 
      else if (value > items[middleIndex])
        {
            firstIndex = middleIndex + 1;
        }
        middleIndex = Math.floor((lastIndex + firstIndex)/2);
    }
    return (items[middleIndex] != value) ? -1 : middleIndex;
}
const items = [1, 2, 3, 4, 5, 7, 8, 9];
console.log(binary_Search(items, 1));   
console.log(binary_Search(items, 5));

Демонстрация в реальном времени:

См. Pen JavaScript - Выполните бинарный поиск в массиве - array-ex- 18 с помощью w3resource ( @ w3resource ) в CodePen .

Улучшите этот пример решения и опубликуйте свой код через Disqus

Предыдущий: Напишите программу JavaScript для перемешивания массива.
Далее: написать программу на JavaScript для вычисления суммы каждого отдельного значения индекса из заданных массивов.