Бинарный поиск - это алгоритм разделяй и властвуй. Как и все алгоритмы разделяй и властвуй, двоичный поиск сначала делит большой массив на два меньших подмассива, а затем рекурсивно (или итеративно) управляет подмассивами. Но вместо того, чтобы работать с обоими подмассивами, он отбрасывает один подмассив и продолжает работу со вторым подмассивом. Решение об отказе от одного подмассива принимается всего за одно сравнение.

Таким образом, двоичный поиск в основном сокращает пространство поиска вдвое на каждом этапе. Под пространством поиска мы подразумеваем подмассив данного массива, в котором находится целевое значение (если оно присутствует в массиве). Первоначально пространство поиска представляет собой весь массив, а двоичный поиск переопределяет пространство поиска на каждом шаге алгоритма, используя свойство массива, в котором он сортируется. Это делается путем сравнения среднего значения в пространстве поиска с целевым значением. Если целевое значение соответствует среднему элементу, возвращается его позиция в массиве. В противном случае он отбрасывает половину пространства поиска на основе результата сравнения.

В этом посте мы перечислили часто задаваемые вопросы на собеседовании, в которых используется алгоритм двоичного поиска:

  1. Алгоритм двоичного поиска
  2. Найти количество поворотов в отсортированном по кругу массиве
  3. Искать элемент в массиве с круговой сортировкой
  4. Найти первое или последнее вхождение данного числа в отсортированном массиве
  5. Подсчитать количество вхождений числа в отсортированном массиве с дубликатами
  6. Найти наименьший недостающий элемент в отсортированном массиве
  7. Найти пол и конец числа в отсортированном целочисленном массиве
  8. Искать в почти отсортированном массиве за логарифмическое время
  9. Найти количество единиц в отсортированном двоичном массиве
  10. Найти пиковый элемент в массиве
  11. Найти пропущенный член в последовательности за логарифмическое время
  12. Найти пол и конец числа в отсортированном массиве (Рекурсивное решение)
  13. Найти частоту каждого элемента в отсортированном массиве, содержащем дубликаты
  14. Найдите квадратный корень из числа с помощью двоичного поиска
  15. Деление двух чисел с помощью алгоритма двоичного поиска
  16. Найти нечетно встречающийся элемент в массиве за логарифмическое время
  17. Найти пары с разностью` k` в массиве | Постоянное космическое решение
  18. Найти` k` ближайших элементов к заданному значению в массиве
  19. Бинарный поиск в C ++ STL и Java-коллекциях
  20. Тернарный поиск против двоичного поиска
  21. Экспоненциальный поиск
  22. Неограниченный двоичный поиск