Интерполирующий поиск на С++

В этой теме 0 ответов, 1 участник, последнее обновление  Васильев Владимир Сергеевич 1 месяц, 1 неделя назад.

  • Автор
    Сообщения
  • #5568
    @admin

    Как эффективно найти число в массиве? — если мы ничего не знаем об элементах массива, то ничего лучше последовательного перебора элементов придумать нельзя. Если нам известно, что числа в массиве упорядочены — то можно применить двоичный поиск. Оба алгоритма подробно описаны в этой статье.

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

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

    int interpolatingSearch (int a[], int arraySize, int keyOfSearch) {
      //изначально устанавливаем нижний индекс на начало массива,
      //а верний на конец массива
      int low = 0;
      int high = arraySize - 1;
      int mid;
    
      while (a[low] < keyOfSearch && a[high] >= keyOfSearch) {
        //оценка новой области поиска
        //по расстоянию между ключом поиска и текущим значение элемента
        mid = low + ((keyOfSearch - a[low]) * (high - low)) / (a[high] - a[low]);
    
        //если значение в ячейке с индексом mid меньше, то смещаем нижнюю границу
        if (a[mid] < keyOfSearch) {
          low = mid + 1;
        }
        //в случае, если значение больше, то смещаем верхнюю границу
        else {
          if (a[mid] > keyOfSearch) {
            high = mid - 1;
          else
            return mid;
          }
        }
      }
      //если цикл while не вернул индекс искомого значения,
      //то проверяем не находится ли оно в ячейке массива с индексом low,
      //иначе возвращаем -1 (значение не найдено)
      if (a[low] == keyOfSearch)
        return low;
      return -1;
    }

Для ответа в этой теме необходимо авторизоваться.