Двоичный (бинарный) поиск

Двоичный (бинарный) поиск (также известен как метод деления пополам и дихотомия) — классический алгоритм поиска элемента в отсортированном массиве (векторе), использующий дробление массива на половины .
Сложность алгоритма log^2(n) (это меньше чем просто n).
Время выполнения алгоритма логарифмическое (это меньше чем линейное).
Примерно посчитать количество шагов можно размер массива значений разделить на два и еще на два и т.д. (if arr.length==100 then 1. 50/2 , 2. 25/2 , 3. 13/2 , 4. 7/2 , 5. 4/2 , 6. 2/2, 7. 1 ... получается примерно 7 шагов).

Код на Java :

Код на C :

Код на JavaScript :


//// Binary search function using JavaScript

/// Defining function
function binSearch(arr, toFind)
{
    /// Checking our array for emptiness.
    if (!arr) return null;
    var first = 0;
    var last = arr.length - 1;
    /// Running binary search
    while (first < last)
    {
        var mid = first + Math.floor((last - first) / 2);
        if (arr[mid] >= toFind) last = mid;
        else first = mid + 1;
    }
    /// After the end of the loop, lastIndex can point to the search item. 
    /// Otherwise the element is missing in the array.
    if (arr[last] == toFind)
        return last;
    else return null;
}

/// Let's try out our function:
console.log(binSearch([1, 2, 4],  4 )); // Output is: 2
console.log(binSearch([1, 2, 4],  3 )); // Output is: null
console.log(binSearch([1, 2, 4],  2 )); // Output is: 1
console.log(binSearch([           ],  1 )); // Output is: null
console.log(binSearch("abcdef",'c')); // Output is: 2

Главная

Алгоритмы

Двоичный (бинарный) поиск