7

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

Почему-то я решил поискать код, решающий эту проблему в сети (через google). Естественно, мне тут же попались equal_range(), lower_bound и upper_bound из C++. Но мне то хотелось найти готовый эквивалент equal_range именно на Си и просто скопипастить его.

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

Интересно, это я гуглить не умею или такую простую штуку никто не удосужился выложить в сеть?

Вот код. Может кому-нибудь пригодиться.

void *
bsearcher (const void *key, const void *base, size_t nmemb, size_t size,
             int (*comp)(const void *key, const void *item), size_t *ipos)
{
  if (ipos)
    *ipos = 0;
  if (!nmemb || !size)
    return 0;

  size_t first = 0, last = nmemb, mid, res;

  while (first < last) {
    mid = first + (last - first) / 2; // by reason of overflow!!!
    if (comp(key, (char *)base + mid * size) > 0)
      first = mid + 1;
    else
      last = mid;
  }

  if ((res = first++) < nmemb  && comp(key, (char *)base + res * size) == 0) {
    //    puts("first key FOUND!"); // yes, it's the comment (just unusual form)
    if (first < nmemb) {
      if (comp(key, (char *)base + first * size) == 0) {
        //      puts ("Have more..., looking for last");
        last = nmemb;
        while (first < last) {
          mid = first + (last - first) / 2; 
          if (comp(key, (char *)base + mid * size) < 0)
            last = mid;
          else
            first = mid + 1;
        }
      }
      if (ipos)
        *ipos = first;
    } else {
      //      puts ("last in array");
      if (ipos)
        *ipos = nmemb;
    }
  } else {
    //    puts("Not Found!");
    if (ipos)
      *ipos = res;
    return 0;
  }

  return (void *)((char *)base + res * size);
}

А здесь, в пастебине он же с тестовым примерчиком.

Функция почти совпадает с bsearch (man 3 bsearch), но всегда (если ключ найден) возвращает указатель на первое его вхождение в массив, плюс в последнем параметре возвращается индекс в массиве после последнего вхождения ключа в массив (т.е. мы получаем искомый диапазон). Если ключ не найден, то в этом параметре будет индекс элемента массива в который можно вставлять искомый ключ.

Update

Для полноты решил добавить (в пастебине тоже отредактировал) пару функций: bsearch_lb() и bsearch_ub() для поиска первого и последнего вхождения в массив ключа, соответственно. Просто каждая из них выполняет свою задачу чуть более эфеективно, чем более общая bsearcher() (а возможно, кому-то просто будет интересно посмотреть на алгоритмы поиска в "чистом виде").

Если ключ найден, то bsearch_lb() в аргументе ipos возвращает позицию (индекс в массиве) найденного элемента. В остальном поведение этих функций аналогично bsearcher().

void *
bsearch_lb (const void *key, const void *base, size_t nmemb, size_t size,
             int (*comp)(const void *key, const void *item), size_t *ipos)
{
  if (ipos)
    *ipos = 0;
  if (!nmemb || !size)
    return 0;

  size_t first = 0, last = nmemb, mid;

  while (first < last) {
    mid = first + (last - first) / 2; // by reason of overflow!!!
    if (comp(key, (char *)base + mid * size) > 0)
      first = mid + 1;
    else
      last = mid;
  }
  if (ipos)
    *ipos = first;

  if (first < nmemb  && comp(key, (char *)base + first * size) == 0)
    return (void *)((char *)base + first * size);
  return 0;
}

void *
bsearch_ub (const void *key, const void *base, size_t nmemb, size_t size,
             int (*comp)(const void *key, const void *item), size_t *ipos)
{
  if (ipos)
    *ipos = 0;
  if (!nmemb || !size)
    return 0;

  size_t first = 0, last = nmemb, mid;

  while (first < last) {
    mid = first + (last - first) / 2; 
    if (comp(key, (char *)base + mid * size) < 0)
      last = mid;
    else
      first = mid + 1;
  }
  if (ipos)
    *ipos = first;

  if (first && comp(key, (char *)base + --first * size) == 0)
    return (void *)((char *)base + first * size);
  return 0;
}

Конечно, это сообщение не похоже на вопрос и ответов не требует. Возможно, его место в исследованиях (хотя, исследованием тут тоже и не пахнет).

3
  • Вот обсуждение на SO.
    – VladD
    20 мая 2014 в 21:23
  • 1
    @VladD, возможно я его видел, разве только вот сюда из него точно не добирался. Но, тут же тоже ведь не generic. Собственно, само написание кода (даже со всеми проверками) пожалуй заняло меньше времени, чем чтение всего, что попадалось при поиске (но я не жалуюсь, некоторые материалы были весьма интересными, хотя, как часто и бывает, может прямо и не относящимися к делу).
    – avp
    20 мая 2014 в 21:49
  • @avp: для меня было новостью, что код без проверок на равенство автоматически выводит на левую границу.
    – VladD
    21 мая 2014 в 8:45

1 ответ 1

1

Посмотри любую!!! реализацию бинарного поиске не через три пути (меньше , равно , больше) - (начни с Бентли Жемчужины программирования)

а через два пути меньше и больше где равно прислоняют к одному из вариантов а условие выхода единственное когда границе перестают быть инвариантом ( l<r)

с дополнительной проверкой l-ный элемент искомое или мы нашли позицию куда поместится искомое в случае вставки ( у Степанова в видео лекциях есть обсуждение почему общепринятый интерфейс бинарного поиска возвращающий специальный (-1 или NULL или ещё чё) в случае отсутствия искомого есть плохой интерфейс)

обычно такие поиске работают на полуоткрытых интервалах (включая L , не включая R)

о пользе полуоткрытых интервалов много у Голуба(верёвка достаточной длины - у него есть как раз набор статей об полуоткрытых интервалах на сайте доктор доба) , Коенига (С traps), Степанова (автор STL)

2
  • 1
    @qulinxao, а Вы код-то (и весь текст "вопроса") читали?
    – avp
    21 мая 2014 в 20:56
  • ,было странно обнаружить , что код который всегда даёт границу( в зависимости от к какой ветке из двух относят равенство) назван дающим любой равный. после ответа внимательней посмотрел вопрос и в недоумении - в чём вообще затруднение? штатный бсёч даёт границу ( и в standard C89 вроде даже обгаварено какую).
    – qulinxao
    21 мая 2014 в 22:41

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.