Двоичный поиск — это алгоритм, позволяющий быстро найти элемент в отсортированном списке элементов. Он работает путем многократного деления списка пополам и проверки того, в какой половине находится элемент. Этот процесс повторяется до тех пор, пока элемент не будет найден или не будет определено, что элемент отсутствует в списке.

В этом уроке мы узнаем, как реализовать бинарный поиск в Swift и поймем, как он работает.

Выполнение:

Во-первых, давайте начнем с создания функции, которая принимает отсортированный массив и элемент, который мы хотим найти, в качестве аргументов.

func binarySearch(array: [Int], element: Int) -> Int? {
    // code goes here
}

Далее мы инициализируем две переменные, low и high, которые будут представлять нижнюю и верхнюю границы массива, в котором мы ищем. Эти переменные будут использоваться для определения среднего элемента массива на каждой итерации поиска.

func binarySearch(array: [Int], element: Int) -> Int? {
    var low = 0
    var high = array.count - 1
    
    // code goes here
}

Теперь мы создадим цикл while, который будет выполняться до тех пор, пока low не станет меньше или равно high. Внутри цикла мы вычислим средний индекс массива, взяв среднее значение low и high. Затем мы проверим, является ли элемент в среднем индексе тем, который мы ищем. Если это так, мы вернем индекс.

func binarySearch(array: [Int], element: Int) -> Int? {
    var low = 0
    var high = array.count - 1
    
    while low <= high {
        let mid = (low + high) / 2
        if array[mid] == element {
            return mid
        }
        
        // code goes here
    }
}

Если элемент в среднем индексе не тот, который мы ищем, нам нужно определить, в какой половине массива мы должны искать. Если элемент, который мы ищем, меньше, чем элемент в среднем индексе, мы знаем это должен находиться в левой половине массива, поэтому мы обновляем high до среднего индекса - 1. Если искомый элемент больше, чем элемент в среднем индексе, мы знаем, что он должен находиться в правой половине массива. массив, поэтому мы обновляем low как средний индекс + 1.

func binarySearch(array: [Int], element: Int) -> Int? {
    var low = 0
    var high = array.count - 1
    
    while low <= high {
        let mid = (low + high) / 2
        if array[mid] == element {
            return mid
        }
        
        if array[mid] > element {
            high = mid - 1
        } else {
            low = mid + 1
        }
    }
}

Наконец, нам нужно добавить оператор return вне цикла while для обработки случая, когда элемент не найден в массиве.

func binarySearch(array: [Int], element: Int) -> Int? {
    var low = 0
    var high = array.count - 1
    
    while low <= high {
        let mid = (low + high) / 2
        if array[mid] == element {
          return mid
        }
        if array[mid] > element {
          high = mid - 1
        } else {
          low = mid + 1
        }
    }

    return nil
}

Вот и все! Теперь вы можете использовать функцию `binarySearch` для поиска элемента в отсортированном массиве.

Вот пример использования функции:

let array = [1, 2, 3, 4, 5, 6, 7, 8, 9]
let element = 5

if let index = binarySearch(array: array, element: element) {
    print("Element found at index: (index)")
} else {
    print("Element not found")
}

Выход:

Element found at index: 4

Объяснение:

Алгоритм бинарного поиска работает, разделяя массив пополам и проверяя, в какой половине находится элемент. На каждой итерации он вычисляет средний индекс массива и сравнивает элемент по этому индексу с элементом, который мы ищем. Если они равны, поиск завершается и возвращается индекс. Если элемент, который мы ищем, меньше, чем элемент со средним индексом, мы знаем, что он должен быть в левой половине массива, и мы обновляем переменную `high`, чтобы она была средним индексом — 1. Если элемент, который мы ищем, поиск больше, чем элемент в среднем индексе, мы знаем, что он должен быть в правой половине массива, и мы обновляем переменную `low`, чтобы она была средним индексом + 1. Этот процесс повторяется до тех пор, пока элемент не будет найден или определяется, что элемент отсутствует в массиве.

Заключение:

В этом уроке мы узнали, как реализовать бинарный поиск в Swift и поняли, как он работает. Двоичный поиск — это эффективный способ поиска элемента в отсортированном списке элементов, который часто используется в информатике и разработке программного обеспечения. Если вы хотите узнать больше о бинарном поиске и других алгоритмах, вы можете воспользоваться следующими ресурсами: