Двоичный поиск в Swift и расширение возможностей коллекций

Многие из нас изучали алгоритмы, но не многие реализовывали их на практике. 

Стандартная библиотека (Foundation для Swift) предлагает готовые методы и функции, которые сами реализуют эти алгоритмы. Не думаю, что многим доводилось прописывать quicksort, но мы ежедневно используем такие методы, как sort.

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

Примечание: знание этих алгоритмов и принципа их работы окажется на руку любому разработчику ПО. Даже если нам и не придется их реализовывать, они могут дать подсказки к решению аналогичных задач.

Двоичный поиск

Мы будем работать с алгоритмом двоичного поиска.

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

У алгоритма есть строгое требование: коллекция должна быть упорядочена. По всей видимости, из-за этого он и не был реализован в Foundation. Тем не менее в реальности есть несколько случаев, где мы работаем с упорядоченными данными: при поиске конкретной даты в историческом датасете, при поиске коммита, а также при поиске человека в отсортированном списке.

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

В первую очередь мы реализуем скелет и глобальную функцию. Затем мы обобщим все это и расширим возможности. Вот код:

func recursiveBinarySearch(nums: [Int], target: Int) -> Int? {
  func _recursiveBinarySearch(nums: [Int], target: Int, start: Int, end: Int) -> Int? {
  }
  
  return _recursiveBinarySearch(nums: nums, target: target, start: 0, end: nums.count - 1)
}

Он представляет публичный интерфейс функции (API) и его структуру. Этот API получает массив чисел nums и элемент target. Возвращает он индекс искомого элемента, если таковой существует. В противном случае ответом будет nil. Внутри для запуска поиска мы вызываем рекурсивную функцию с соответствующими индексами начала и конца.

Будьте внимательны к индексам. Мы будем использовать их оба для обращения к массиву, поэтому передаем в качестве конечного индекса значение count-1.

Алгоритм

При написании рекурсивного алгоритма изначально нужно определить базовый кейс: “Когда и как рекурсия должна заканчиваться?” В нашем случае она продолжается, пока стартовый индекс не станет больше конечного. В этот момент мы возвращаем nil: цель (target) не может находится в этом диапазоне, так как он является нулевым. Вот код:

func recursiveBinarySearch(nums: [Int], target: Int) -> Int? {
  func _recursiveBinarySearch(nums: [Int], target: Int, start: Int, end: Int) -> Int? {
    // Базовый кейс. Не забудьте о равенстве!
    guard start <= end else {
      return nil
    }
    
    // Выбрать элемент в середине
    let midIndex = (start+end)/2
    let mid = nums[midIndex]
    
    if mid == target {
      // второй базовый кейс: элемент найден!
      return midIndex
    } else if target < mid {
      // просмотр нижней части массива
      return _recursiveBinarySearch(nums: nums, target: target, start: start, end: midIndex - 1)
    } else {
      // просмотр верхней части массива
      return _recursiveBinarySearch(nums: nums, target: target, start: midIndex + 1, end: end)
    }
  }
  
  return _recursiveBinarySearch(nums: nums, target: target, start: 0, end: nums.count - 1)
}

После определения базового кейса мы переходим к логике. Здесь у нас три шага:

1. Извлечение среднего индекса и его значения.
2. Сравнение среднего значения с целевым.
3. Определение, было ли найдено целевое значение, или же нужно продолжить поиск. Если поиск продолжается, то в какую сторону принимается решение.

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

Обобщение поиска

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

Конечно же, мы не станем повторно реализовывать алгоритм для всевозможных типов данных. Можно задействовать обобщения, чтобы написать его один раз, и затем использовать для каждого типа.

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

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

func recursiveBinarySearch<T: Comparable>(values: [T], target: T) -> Int? {
  func _recursiveBinarySearch<T: Comparable>(values: [T], target: T, start: Int, end: Int) -> Int? {
    // Базовый кейс. Не забудьте о равенстве!
    guard start <= end else {
      return nil
    }
    
    // Выбираем элемент в середине
    let midIndex = (start+end)/2
    let mid = values[midIndex]
    
    if mid == target {
      // второй базовый кейс: элемент найден!
      return midIndex
    } else if target < mid {
      // просматриваем нижнюю часть массива
      return _recursiveBinarySearch(values: values, target: target, start: start, end: midIndex - 1)
    } else {
      // просматриваем верхнюю часть массива
      return _recursiveBinarySearch(values: values, target: target, start: midIndex + 1, end: end)
    }
  }
  
  return _recursiveBinarySearch(values: values, target: target, start: 0, end: values.count - 1)
}

Этот вариант алгоритма идентичен предыдущему. Единственное отличие в том, что массив и цель являются обобщениями в T, а T подчиняется протоколу Comparable. С помощью такого простого изменения мы получили алгоритм, который можно выполнять для любого массива Comparable (сравнимых) типов.

Расширение возможностей коллекций

Есть еще пара небольших нюансов, которые следует доработать. Во-первых, мы опираемся на глобальную функцию. 

Чтобы использовать алгоритм нам нужно написать код таким образом:

let array = [0,3, 6, 8, 14, 78, 123, 13467, 134566]
let target = 14
let found = recursiveBinarySearch(values: array, target: target)

Здесь, конечно, ошибок нет, но такой код не совсем в стиле Swift. Наша задача получить синтаксис вроде array.binarySearch(target).

Для этого можно расширить протокол коллекций, который позволяет обращаться к ним по индексу. За предоставление этой возможности отвечает протокол RandomAccessCollection. Помимо типа index он определяет сабскрипт, необходимый для реализации двоичного поиска.

Вторая доработка подразумевает гарантию выполнения предварительного условия упорядоченности.

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

extension RandomAccessCollection where Element: Comparable {

  var isSorted: Bool {
    for i in 0..<self.count - 2 {
      let firstValue = self[self.index(self.startIndex, offsetBy: i)]
      let secondValue = self[self.index(self.startIndex, offsetBy: i+1)]
      if firstValue > secondValue {
        return false
      }
    }
    return true
  }

  func recursiveBinarySearch(target: Element) -> Int? {
    assert(self.isSorted)

    func _recursiveBinarySearch(target: Element, start: Int, end: Int) -> Int? {
      // Базовый кейс. Не забудьте о равенстве!
      guard start <= end else {
        return nil
      }

      // Выбираем элемент в середине
      let midIndex = (start+end)/2
      let mid = self[self.index(self.startIndex, offsetBy: midIndex)]

      if mid == target {
        // второй базовый кейс: элемент найден!
        return midIndex
      } else if target < mid {
        // просматриваем нижнюю часть массива
        return _recursiveBinarySearch(target: target, start: start, end: midIndex - 1)
      } else {
        // просматриваем верхнюю часть массива
        return _recursiveBinarySearch(target: target, start: midIndex + 1, end: end)
      }
    }

    return _recursiveBinarySearch(target: target, start: 0, end: self.count - 1)
  }
}

Эту версию алгоритма можно вызвать с помощью collection.recursiveBinarySearch(target:). collection  —  это все, что соответствует протоколу RandomAccessCollection и содержит какой-либо Comparable тип.

Инструкция assert на строке 15 обеспечивает упорядоченность коллекции. Эта проверка активна только, когда приложение собирается с конфигурацией Debug. Она гарантирует упорядоченность коллекции при тестировании приложения, давая сбой при невыполнении этого предварительного условия. Однако при конфигурации Release эта инструкции всегда вычисляется как true.

В случае обнаружения искомого элемента функция возвращает смещение из startIndex. При работе с RandomAccessCollection вместо простого использования значений int с индексами приходится повозиться. Несмотря на свою кажущуюся громоздкость, на деле такой подход оказывается более типобезопасен и позволяет выполнять двоичный поиск для коллекций, где индекс выражен не в int. Еще один дополнительный уровень обобщения.

Сложность

При реализации алгоритма важно задуматься о его временной и пространственной сложности. Это меры того, как долго он выполняется для входных данных определенного размера, и сколько памяти он занимает сверх этих данных. Такой анализ известен как нотация “О” большое.

Дано n входных элементов. Мы рекурсивно разделяем их массив пополам. Это означает, что во второй итерации у нас получится вход n/2, а в третьей n/4. Далее размер входных данных уменьшается до n/8, n/16 и т.д.

Конечный результат выглядит как необходимость выполнения log2(n) операций. С помощью нотации большого О временная сложность определяется как O(logN). Это неплохое время выполнения для алгоритма, так как он оказывается быстрее, чем любой линейный поиск.

При рассмотрении пространственной сложности нужно задействовать несколько переменных для хранения определенных индексов. Изначально можно предположить, что мы работаем с постоянным пространством, O(1). Однако нельзя забывать, что у нас рекурсивный алгоритм. Каждый раз при входе в рекурсию мы задействуем несколько адресов памяти для стека вызовов функции. С учетом того, что мы используем logN рекурсий, двоичный поиск занимает O(logN) памяти.

Итеративный подход

К нашему удобству рекурсивный подход не единственный. Каждый рекурсивный алгоритм можно написать итеративным способом и наоборот.

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

Нижеприведенный алгоритм представляет итеративный вариант двоичного поиска:

func iterativeBinarySearch(nums: [Int], target: Int) -> Int? {
  guard !nums.isEmpty else {
    return nil
  }
   
  var start = 0
  var end = nums.count - 1
  while start <= end {
    var middleIndex = (start + end) / 2
    var middleValue = nums[middleIndex]
    
    if middleValue == target {
      return middleIndex
    } else if target < middleValue {
      // ищем в левой части массива
      end = middleIndex - 1
    } else {
      // ищем в левой части массива
      start = middleIndex + 1
    }
  }
  
  return nil
}

Этот код проще, чем предыдущий рекурсивный вариант. Здесь у нас также три этапа:

• Проверка массива на пустоту.
• Выполнение перебора, пока стартовый индекс не окажется меньше или равен конечному индексу.
• Обновление стартового и конечного индексов в зависимости от того, в какой части массива нужно продолжить поиск при следующей итерации.

Я решил показать глобальную версию итеративного подхода. Это хорошее упражнение для его расширения с помощью обобщений, и протокола Comparable с последующим перемещением в RandomAccessCollection.

Сложность

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

В отношении временной сложности ничего не изменилось. Мы анализируем половину массива при каждой итерации. Временная сложность остается равной O(logN).

Что касается пространственной сложности, то она уже отличается. Мы задействуем несколько простых переменных для индексов, а цикл while не использует дополнительную память. В связи с этим пространственная сложность остается постоянной, то есть O(1).

Заключение

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

Мы также рассмотрели нотацию большого О, важнейшую тему для любого разработчика ПО, и проанализировали две разные версии двоичного поиска. 

Надеюсь, что статья вам понравилась. Подобные знания помогают нам вырасти из хороших программистов в исключительных. Для многих не секрет, что в крупных компаниях вроде Facebook, Amazon, Apple, Netflix и Google на собеседованиях непременно задают вопросы о сложности алгоритмов.

Читайте также:

• Создание кастомного навигационного представления в SwiftUI
• Как работает проверка доступности API в Swift
• Полезные глобальные функции языка Swift

Читайте нас в Telegram, VK и Яндекс.Дзен

---

Перевод статьи Riccardo Cipolleschi: How To Extend Collections in Swift With Binary Search