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

Одно время мы выпускали несложный контроллер облачной СКУД на 100 пользователей. В его основе лежал микроконтроллер PIC18F46K22. В качестве памяти для хранения кодов ключей пользователей использовалась FLASH-память с интерфейсом I^₂C ёмкостью 64 кБ. Сама «флешка» довольно быстрая, но на шине I²C находилась ещё микросхема часов DS1307, которая работает на скорости не выше 100 кбит/сек. Высокой скорости работы нам не требовалось, поэтому в итоге вся шина была запущена на частоте 100 кГц.

Однако со временем мы начали разрабатывать новую версию контроллера, поддерживающего уже 3000 пользователей. Не хотелось сильно менять архитектуру, поэтому основные узлы были сохранены, но при этом был увеличен объём FLASH-памяти до 256 кБ.

И вот тут возник один интересный момент. В первой версии поиск ключа в памяти осуществлялся простым перебором всех 100 ключей. Этот процесс занимал долю секунды и поэтому каких-либо оптимизаций кода не производилось. Но при количестве в 3000 записей это время увеличилось в 30 раз, что оказалось недопустимым, так как у пользователя появлялась неприятная задержка между считыванием карты и открытием замка.

Решить данную проблему можно двумя способами. Первый – аппаратный вариант, предполагающий использование более быстрого интерфейса с «флешкой», например, SPI. Скорости чтения здесь на два порядка выше, чем при использовании I²C. Это, так сказать, решение «в лоб». Неудобство лишь состоит в том, что приходится закладывать в устройство новый компонент, переделывать код и печатную плату. Плюс потребуются дополнительные линии микроконтроллера для подключения такой микросхемы памяти.

Но есть и другой способ – программный. Заключается он в переделке самой процедуры поиска. Изначально она выглядела так:

typedef struct
{
    uint32_t COD;				
    uint8_t nSchedule;
} TSKUD_User;

bool skudFindUserByCode(uint32_t pCOD)
{
  TSKUD_User user;

  for (uint8_t i = 0; i < SKUD_USERS_COUNT; i++)
  {
    skudReadUser(i, &user);

    if (user.COD == pCOD)
      return 1;
  }

  return 0;
}

Функция skudReadUser считывала блок данных из I²C памяти, далее осуществлялась проверка на совпадение кода.

При ста пользователях в худшей случае (когда код находился в самом конце массива данных) время поиска занимало порядка 0,1 сек. При переходе же к 3000 пользователей время выросло 3 сек!

Поэтому для ускорения функция была переписана следующим образом:

bool skudFindUserByCode(uint32_t pCOD)
{
  TSKUD_User user;
  int16_t m, beg, end;

  beg = 0;
  end = SKUD_USERS_COUNT - 1;

  while (beg <= end)
  {
    m = (beg + end) / 2;

    skudReadUser(m, &user);

    if (pCOD == user.COD)
      return true;

    if ((pCOD < user.COD) || (user.COD == 0))
      end = m - 1;
    else
      beg = m + 1;
  }

  return false;
}

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

О различных частных случаях при реализации бинарного поиска можно почитать в статье: «Я не могу написать бинарный поиск».

Итак, рассмотрим работу алгоритма. Переменные beg и end задают начальный и конечный индекс массива данных. На каждой итерации мы вычисляем индекс m, который находится посередине между beg и end, и сравниваем требуемое значения ключа с тем, что находится по этому индексу. В этом случае возможны три варианта:

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

2. Если номер искомой карты меньше, то следует его искать в левой части массива. Тут мы отбрасываем сразу половину заведомо не подходящих вариантов. Индекс end теперь будет равен m – 1.

3. Если номер искомой карты меньше, то следует его искать в правой части массива. Так же отбрасываем сразу половину заведомо не подходящих вариантов, но меняем индекс beg (он будет равен m + 1).

Если в массиве данных вообще нет искомого значения ключа, то нам нужно выйти из цикла. Условием выхода является beg > end.

Очень важным является дополнительное условие user.COD == 0 в строке:

    if ((pCOD < user.COD) || (user.COD == 0))

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

Можно было бы записывать туда значения 0xFFFFFFFF, но его мы используем в качестве сервисного для служебных нужд системы. Поэтому дополнительное условие user.COD == 0 всегда «заставляет» алгоритм искать код в левой половине массива данных.

Кто-то может справедливо заметить, что нет смысла тогда вообще обрабатывать эти нулевые значения. Но дело в том, что мы не передаём в контроллер реальное количество карт доступа. Изначально для 100 карт это не имело смысла (поиск и так работал очень быстро), а потом мы просто не стали менять структуру данных. Но, по большому счёту, это и не нужно, так как бинарный поиск очень сильно ускоряет работу.

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

А вот при бинарном поиске количество сравнений будет составлять log₂3000 ? 11 шт!

Интересно, что если записей будет аж 4 миллиарда, то количество сравнений при использовании бинарного поиска увеличится всего лишь до 32!

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

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

Так в чём преимущество такого решения? В начале статьи я указывал, что алгоритм реализовывался на микроконтроллере. Использование крайне дешёвой памяти с интерфейсом I^₂C снижает общую себестоимость изделия, а новый алгоритм поиска сильно уменьшает время реакции контроллера.

Всегда интересно посмотреть как реализации алгоритмов работают «вживую». Для этого я снял два небольших видео, где показана работа контроллера в двух вариантах: с линейным поиском и бинарным. Нужное значение карты памяти я специально внёс в самый конец списка (индекс 2999), чтобы можно было оценить работы обоих алгоритмов в худшем случае.

Вот работа линейного поиска:

А вот бинарного:

Результат, как говориться, на лицо!