Линейный и бинарный поиск в Clojure

Привет, Хабр!

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

Линейный поиск в Clojure

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

Вот как это выглядит на Clojure:

(defn linear-search [arr target]   (loop [i 0]     (cond       (= i (count arr)) nil ; Если дошли до конца и ничего не нашли, возвращаем nil       (= (nth arr i) target) i ; Если нашли, возвращаем индекс       :else (recur (inc i))))) ; Продолжаем искать 

Здесь я использую loop и recur для перебора массива. Никаких мутаций, всё через рекурсию, чистая функциональщина.

Теперь немного более интересная версия линейного поиска — метод двух указателей. Это когда по массиву можно начать поиск сразу с двух сторон — с начала и конца.

Вот как это делается:

(defn two-pointer-search [arr target]   (loop [left 0 right (dec (count arr))]     (cond       (= left right) (if (= (nth arr left) target) left nil) ; Если указатели встретились       (= (nth arr left) target) left ; Нашли слева       (= (nth arr right) target) right ; Нашли справа       :else (recur (inc left) (dec right))))) ; Двигаем оба указателя

Это немного быстрее, если вы ожидаете, что нужный элемент находится ближе к краям списка.

Помимо этого, часто нужно не просто найти элемент, а проверить наличие элемента, который удовлетворяет определённому условию. Например, нужно найти первое чётное число в массиве.

Пример кода с предикатом:

(defn linear-search-predicate [arr pred]   (loop [i 0]     (cond       (= i (count arr)) nil ; Если ничего не найдено       (pred (nth arr i)) i ; Если условие выполнено, возвращаем индекс       :else (recur (inc i))))) ; Продолжаем искать

Здесь мы передаём предикат в виде функции. Предикат — это просто функция, которая возвращает истину или ложь, например:

(def numbers [1 2 3 4 5 6 7 8 9 10]) (linear-search-predicate numbers even?) ; вернёт 1 (индекс числа 2)

Порой бывает полезно осуществить линейный поиск с пропуском элементов с определённым шагом.

(defn linear-search-step [arr target step]   (loop [i 0]     (cond       (>= i (count arr)) nil ; Если ничего не найдено       (= (nth arr i) target) i ; Если нашли — возвращаем индекс       :else (recur (+ i step))))) ; Пропускаем несколько элементов

Пример использования:

(def nums [1 2 3 4 5 6 7 8 9 10]) (linear-search-step nums 6 2) ; вернёт 5 (индекс "6")

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

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

Пример:

(defn binary-search [arr target]   (loop [low 0 high (dec (count arr))]     (if (<= low high)       (let [mid (quot (+ low high) 2)] ; Находим середину         (cond           (= (nth arr mid) target) mid ; Если нашли — отлично!           (< (nth arr mid) target) (recur (inc mid) high) ; Если середина меньше, ищем справа           :else (recur low (dec mid)))) ; Если больше — ищем слева       nil))) ; Элемент не найден

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

Бинарный поиск не обязательно должен работать только с массивами. Можноадаптировать бинарный поиск под дерево (не то, что растёт в лесу, а бинарное дерево).

Пример бинарного поиска в дереве:

(defrecord Node [value left right])  (defn binary-tree-search [node target]   (cond     (nil? node) nil ; Узел не найден     (= target (:value node)) node ; Если нашли — возвращаем узел     (< target (:value node)) (binary-tree-search (:left node) target) ; Ищем в левом поддереве     :else (binary-tree-search (:right node) target))) ; Ищем в правом поддереве

Тут та же логика, что и для массивов, только вместо индексов – узлы дерева. Двигаемся влево или вправо в зависимости от значения.

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

Пример кода:

(defn interpolation-search [arr target]   (loop [low 0 high (dec (count arr))]     (if (and (<= low high) (<= (nth arr low) target) (>= (nth arr high) target))       (let [pos (+ low (quot (* (- target (nth arr low)) (- high low))                              (- (nth arr high) (nth arr low))))]         (cond           (= (nth arr pos) target) pos ; Если нашли — отлично!           (< (nth arr pos) target) (recur (inc pos) high) ; Если меньше — ищем справа           :else (recur low (dec pos)))) ; Если больше — ищем слева       nil)))

Этот метод работает лучше, если данные равномерно распределены.

А что если нужно найти элемент не в массиве чисел, а, скажем, в отсортированном списке строк? Бинарный поиск адаптируется и для строковых данных:

(defn binary-search-string [arr target]   (loop [low 0 high (dec (count arr))]     (if (<= low high)       (let [mid (quot (+ low high) 2)]         (cond           (= (nth arr mid) target) mid           (neg? (compare (nth arr mid) target)) (recur (inc mid) high)           :else (recur low (dec mid))))       nil))) 

Пример использования:

(def names ["Alice" "Bob" "Charlie" "David" "Eve"]) (binary-search-string names "Charlie") ; вернёт 2 (индекс "Charlie")

Ещё один интересный случай — это бинарный поиск не по конкретному значению, а по условию. Например, нужно найти первый элемент в массиве, который больше какого-то значения.

(defn binary-search-first-greater [arr target]   (loop [low 0 high (dec (count arr))]     (if (<= low high)       (let [mid (quot (+ low high) 2)]         (if (> (nth arr mid) target)           (if (or (zero? mid) (<= (nth arr (dec mid)) target))             mid             (recur low (dec mid)))           (recur (inc mid) high)))       nil)))

Пример использования:

(def nums [1 3 5 7 9 11 13 15]) (binary-search-first-greater nums 6) ; вернёт 3 (индекс первого числа, больше 6, то есть 7)

Заключение

Clojure — удивительно чистый и выразительный язык для таких задач. И хотя функциональный подход может показаться в чем-то сложным поначалу, он позволяет писать код, который легко поддерживать и расширять!

---

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

Приглашаем всех желающих на открытый урок, на котором вы узнаете, как можно добавлять новые функции или менять состояние программы, «прощупывать» любые данные и пошагово отлаживать код, запускать тесты и подключаться к внешним системам. И всё это, не выходя из REPL. Записаться можно по ссылке.