Golang вопросы собеседований

👣 Алгоритмы поиска в Go



Рассмотрим здесь 2 известных алгоритма поиска: линейный и бинарный.



🟡Линейный поиск (Linear Search) — это простой алгоритм поиска элемента в коллекции. Он работает путем последовательного перебора всех элементов до тех пор, пока не будет найден искомый элемент или не будут проверены все элементы.



Алгоритм:

1. Начните с первого элемента списка.

2. Сравните его с искомым элементом.

3. Если элемент совпадает с искомым, верните его индекс

4. Если элемент не совпадает с искомым, перейдите к следующему элементу в списке.

5. Повторяйте шаги 2-4 до тех пор, пока не найдете искомый элемент или не пройдете весь список.



Линейный поиск имеет временную сложность O(n), где n — это количество элементов в списке.





🟡Бинарный поиск (Binary Search) — это эффективный алгоритм поиска элемента в отсортированном списке, массиве и т.д. Использует стратегию "разделяй и властвуй", что позволяет быстро находить искомый элемент.



Алгоритм:

1. Начните с определения границ поиска. Установите начальную границу (left) в начало списка и конечную границу (right) в его конец.

2. Найдите средний элемент между начальной и конечной границей.

3. Сравните средний элемент с искомым значением.

4. Если средний элемент совпадает с искомым значением, возвращаем его индекс

5. Если средний элемент больше искомого значения, обновите конечную границу (right) на позицию перед средним элементом и перейдите к шагу 2.

6. Если средний элемент меньше искомого значения, обновите начальную границу (left) на позицию после среднего элемента и перейдите к шагу 2.

7. Повторяйте шаги 2-6 до тех пор, пока не будет найден искомый элемент или пока начальная граница (left) не станет больше конечной границы (right).



Бинарный поиск имеет временную сложность O(log n), где n - это количество элементов в списке. Это означает, что в худшем случае алгоритм будет выполняться за логарифмическое время, что является значительно более эффективным, чем линейный поиск.



@golang_interview