Бинарный поиск (binary search)

Бинарный (двоичный) поиск это алгоритм, который позволяет найти элемент в отсортированном массиве за логарифмическое время log n, где n — количество элементов в массиве.

Алгоритм

1. Выбираем средний элемент массива
2. Сравниваем элемент с искомым элементом
3. Если элементы равны, возвращаем индекс этого элемента, иначе:
• Если искомый элемент меньше среднего — просматриваем левую половину массива
• Если искомый элемент больше среднего — просматриваем правую половину массива
4. Применяем алгоритм к выбранной половине массива, пока не найдем элемент
5. Если искомого элемента в массиве нет — выходим из цикла

Код

function search(nums: number[], target: number): number {    
    let start = 0    
    let end = nums.length - 1
    
    while (start <= end) {        
       const key = Math.floor((start + end) / 2)       
       const value = nums[key]

       if (value === target) 
          return key  

       if (target > value) start = key + 1  
       if (target < value) end = key - 1
    }
    
    return -1
}

Применение

Бинарный поиск особенно эффективен при большом количестве элементов, так как он сокращает количество операций сравнения на каждом шаге примерно вдвое.

Тестирование

Среди 100000 элементов:

Среднее время бинарного поиска: 0.006700000077486038 ms
Среднее время indexOf: 4.752699999839067 ms

https://gist.github.com/toastyboost/166424a59659837104b9eecd8bb72289

Вопросы

• Почему в коде используется cursor + 1 и cursor - 1 ?
• Какова сложность алгоритма?

Задачи

• https://leetcode.com/problems/binary-search
• https://leetcode.com/problems/guess-number-higher-or-lower
• https://leetcode.com/problems/search-a-2d-matrix
• https://leetcode.com/problems/search-in-rotated-sorted-array
• https://leetcode.com/problems/find-minimum-in-rotated-sorted-array
• https://leetcode.com/problems/search-in-rotated-sorted-array-ii