Попытка найти программу двоичного поиска на Си в google

#c #google

Несколько дней назад мне понадобилось искать в программе на Си строки с заданным
префиксом в отсортированном массиве. Очевидно, что родной 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;
}


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

Ответы

Ответ 1

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