Если вы новичок в программировании или алгоритмическом мышлении, вам следует изучить два основных алгоритма: бинарный поиск и быструю сортировку. Эти алгоритмы широко используются в компьютерных науках и имеют множество приложений в реальном мире.

В этой статье я предоставлю подробное руководство по бинарному поиску и быстрой сортировке, включая их реализацию, примеры использования и реальные приложения. Я также приведу примеры и пояснения, которые помогут вам понять эти алгоритмы и то, как они работают.

Итак, являетесь ли вы новичком или опытным программистом, читайте дальше, чтобы узнать больше об этих мощных алгоритмах и о том, как они могут помочь вам решить проблемы в вашем коде и в реальном мире.

Если вы хотите больше узнать об алгоритмах, возможно, вам стоит прочитать книгу «Алгоритмы Grokking: иллюстрированное руководство для программистов и других любознательных людей» Адитьи Бхаргавы .

Бинарный поиск

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

Выполнение

def binary_search(arr, target):
    left = 0
    right = len(arr) - 1

    while left <= right:
        mid = (left + right) // 2

        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1

    return -1

Чтобы найти индекс 7в [1, 2, 3, 4, 5, 6, 7, 8, 9], сравните его со средним элементом 5. Если больше 5, ищите в верхней половине [6, 7, 8, 9]. Если меньше 8, ищите в нижней половине [1, 2, 3, 4, 5, 6]. Как только вы найдете 7, его индекс равен 6.

Случаи использования

1. Поиск элемента в отсортированном списке или поиск индекса элемента в отсортированном списке: двоичный поиск может выполнять обе задачи по O(log n)временной сложности.
2. Поиск элемента в отсортированном списке, ближайшего к заданному значению: используйте двоичный поиск, чтобы найти элемент, равный заданному значению или непосредственно перед или после него.
3. Поиск элемента пика в массиве, отсортированном в порядке возрастания, а затем в порядке убывания: используйте двоичный поиск, чтобы найти элемент пика, который больше, чем его соседи.

1. Двоичный поиск эффективно выполняет поиск в больших базах данных, таких как веб-страницы и медицинские записи, чтобы предоставить пользователям релевантные результаты.
2. Алгоритм используется в компьютерных сетях для быстрого нахождения определенного пакета данных в отсортированном порядке пакетов сетевых данных, а также в финансовой торговле для принятия обоснованных решений на основе конкретных данных в больших наборах данных.
3. Бинарный поиск также используется в машинном обучении для поиска оптимальных гиперпараметров для данной модели и в секвенировании ДНК для выявления конкретных генов или мутаций в больших наборах данных.

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

Выполнение

def quick_sort(arr):
    if len(arr) <= 1:
        return arrp
    else:
        pivot = arr[0]
        left = [x for x in arr[1:] if x <= pivot]
        right = [x for x in arr[1:] if x > pivot]
        return quick_sort(left) + [pivot] + quick_sort(right)

Предположим, у нас есть массив со следующими элементами: [9, 7, 5, 11, 12, 2, 14, 3, 10, 6].

Чтобы отсортировать массив с помощью алгоритма быстрой сортировки, выполните следующие действия:

1. Выберите первый элемент массива в качестве опорного, в данном случае 9.
2. Разделите массив на два подмассива: один подмассив с элементами меньше или равными опорной точке, а другой подмассив с элементами больше опорной.

[9, 7, 5, 11, 12, 2, 14, 3, 10, 6]
 ^ pivot
[7, 5, 2, 3, 6]   [9]   [11, 12, 14, 10]

[7, 5, 2, 3, 6]
 ^ pivot
[5, 2, 3, 6]   [7]
 ^ pivot
[2, 3]   [5]   [6]   [7]
 ^ pivot
[2]   [3]   [5]   [6]   [7]
[2, 3, 5, 6, 7]

[11, 12, 14, 10]
 ^ pivot
[10]   [11]   [12, 14]
               ^ pivot
[10]   [11]   [12]   [14]
[10, 11, 12, 14]

[2, 3, 5, 6, 7]   [9]   [10, 11, 12, 14]
[2, 3, 5, 6, 7, 9, 10, 11, 12, 14]

3. Быстрая сортировка — это классический алгоритм «разделяй и властвуй», используемый в обучении информатике и программировании.
4. Быстрая сортировка полезна в приложениях, где важно использование памяти, таких как встроенные системы и приложения реального времени.

1. Быстрая сортировка обычно используется в базах данных и языках программирования для сортировки больших наборов данных и структур данных.
2. Быстрая сортировка используется в научных вычислениях и численном анализе для сортировки больших наборов данных, созданных в ходе моделирования и экспериментов.
3. Быстрая сортировка полезна в электронной коммерции для быстрой сортировки продуктов, обзоров и других данных на основе предпочтений пользователя. Это полезно для интернет-магазинов с большими каталогами.

Двоичный поиск и быстрая сортировка — два фундаментальных алгоритма, которые должен знать каждый программист. Двоичный поиск — это алгоритм поиска, который помогает находить определенные элементы в компьютерных программах, а быстрая сортировка — это алгоритм сортировки, который может эффективно сортировать большие наборы данных. Оба алгоритма имеют множество реальных применений, от поиска в базах данных и финансовой торговли до машинного обучения и секвенирования ДНК. В этой статье я предоставляю подробное руководство по обоим алгоритмам, включая их реализации, варианты использования и реальные приложения. Являетесь ли вы новичком или опытным программистом, эти мощные алгоритмы могут помочь вам решить проблемы в вашем коде и в реальном мире. Если вы хотите узнать больше об алгоритмах, вы можете прочитать книгу«Алгоритмы Grokking: иллюстрированное руководство для программистов и других любознательных людей» Адитья Бхаргава .

В следующей статье я расскажу о другом популярном алгоритме: BFS (поиск в ширину). Этот алгоритм используется для исследования всех вершин графа.