4874

Поиск в массивах. Последовательный, бинарный и интерполяционный поиск

Лекция

Информатика, кибернетика и программирование

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

Русский

2012-11-28

48.5 KB

107 чел.

Поиск в массивах. Последовательный, бинарный и интерполяционный поиск.

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

// Последовательный поиск

// A - указатель на массив

// N - размер массива

// d - искомый элемент

int serialSearch( double * A, int N, double d )

{

 // Индекс по умолчанию, при неудачном поиске

 int index = -1;

 

 for ( int i = 0; i < N; ++i )

 {

 // Нашли искомый элемент

 if ( A[i] == d )

 {

  index = i;

  break;

 }

}

 return index;

}

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

  •  если элемент массива оказался больше искомого, будем искать элемент в «левой» половине текущего диапазона;
  •  если элемент массива оказался меньше искомого, будем искать элемент в «правой» половине текущего диапазона;
  •  если элемент массива совпадает с искомым – поиск успешно завершается;
  •  если диапазон поиска на текущем шаге уменьшился до 1 – искомый элемент в массиве отсутствует, поиск завершается.

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

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

// A - указатель на массив

// N - размер массива

// d - искомый элемент

int binarySearch( double * A, int N, double d )

{

 // Индекс по умолчанию, при неудачном поиске

 int index = -1;

 

 // Индексы нижней и верхней границы диапазона поиска

 int lowerIndex = 0;

 int upperIndex = N-1;

 

 do

{

 // Середина текущего диапазона поиска

 int midIndex = ( upperIndex + lowerIndex ) / 2;

 // Определяем новый диапазон поиска

 if ( A[ midIndex ] > d )

  upperIndex = midIndex;

 else if ( A[ midIndex ] < d )

  lowerIndex = midIndex;

 else // искомый элемент - в середине текущего диапазона

 {

  index = midIndex;

  break;

 }

}

 while( upperIndex - lowerIndex > 1 );

 return index;

}

Алгоритм бинарного поиска обладает недостатком, связанным с тем, что при вычислении очередного «суженного» диапазона поиска никак не учитывается величина искомого элемента и величины элементов, находящихся на границах интервала. Если предположить, что данные в массиве не только упорядочены, но и распределены достаточно «равномерно», то можно значительно ускорить «сходимость» процесса поиска, осуществляя дробление интервала поиска из следующих неформальных соображений: если предположить, что элементы массива принимают значения от 1 до 1000 и нам необходимо найти число 10, то при первом шаге дробления всего диапазона поиска гораздо эффективнее делить его не пополам (учитывая предположение о «равномерности» распределения данных в массиве, новые интервалы будут содержать значения приблизительно 1-500 и 501-1000), а взять «левый» интервал более узким, т.к. предположительно, число 10 окажется гораздо ближе к левой границе исходного диапазона. Более строго, формулу для вычисления индекса, соответствующего разбиению интервала, можно вывести из следующих простых соображений:

Реализация интерполяционного алгоритма поиска приведена ниже.

// Интерполяционный поиск

// A - указатель на массив

// N - размер массива

// d - искомый элемент

int interpSearch( double * A, int N, double d )

{

 // Индекс по умолчанию, при неудачном поиске

 int index = -1;

 

 // Индексы нижней и верхней границы диапазона поиска

 int lowerIndex = 0;

 int upperIndex = N-1;

 

 do

{

 // Индекс разбиения текущего интервала

 int divIndex = lowerIndex;

 

 // Проверка на "вырожденный" случай

 if ( A[upperIndex] != A[lowerIndex] )

  divIndex = lowerIndex + ( upperIndex - lowerIndex ) * ( d - A[lowerIndex] ) / ( A[upperIndex] - A[lowerIndex] );

 else if ( A[lowerIndex ] != d )

  break;

 // Определяем новый диапазон поиска

 if ( A[ divIndex ] > d )

  upperIndex = divIndex;

 else if ( A[ divIndex ] < d )

  lowerIndex = divIndex;

 else // искомый элемент оказался в точке разбиения

 {

  index = divIndex;

  break;

 }

}

 while( upperIndex - lowerIndex > 1 );

 

 return index;

}


iL

R

iX

AL

AR

X

индексы

значения


 

А также другие работы, которые могут Вас заинтересовать

37723. Подготовка изображений для WEB 3.35 MB
  Изображения в сети также важны как и в любом печатном издании. Изображения должны быть правильно отмасштабированы иметь хорошую четкость и сохранены в цветовом пространстве sRGB. Поэтому для получения хороших результатов при сайтостроительстве нужно корректно отмасштабировать изображения перед помещением их в сеть. В Интернет используются изображения с цветовым пространством sRGB.
37724. Создание Форм В INKSCAPE 874 KB
  Для этого щелкните по верхней линейке и перетащите вниз чтобы создать горизонтальную направляющую и щелкните по левой линейке и перетащите вправо чтобы создать вертикальную направляющую см. Выберите инструмент Рисовать круги эллипсы и дуги F5 и щелкните на значке Заливка в правом верхнем углу. Щелкните правой кнопкой мышки на круг и нажмите Продублировать CtrlD. Затем в окне трансформации установите 80 в поле Ширина и щелкните по кнопке pply.
37725. Создание трехмерного Текста в Inkscape 787 KB
  Выберите инструмент Создавать и править текстовые объекты F8 и введите на лист Вашу фамилию. Теперь добавим эффект перспективы к тексту и придадим трехмерность. Инструментом Выделять и трансформировать объекты F1 можно нажать пробел выделите текст и выполните команду Контуры Оконтурить объект ShiftCtrlС.
37726. ВИМІРЮВАННЯ ПАРАМЕТРІВ ІМПУЛЬСНИХ СИГНАЛІВ МЕТОДОМ ДИСКРЕТНОГО РАХУНКУ 132 KB
  ОСНОВНІ ТЕОРЕТИЧНІ ВІДОМОСТІ Методи вимірювання частоти і інтервалів часу різноманітні. Застосовуються методи безпосереднього вимірювання методи засновані на порівнянні частоти зі зразковою частотою за допомогою осцилографа гетеродинний нульове биття і резонансний методи. Метод вимірювання Вхідний сигнал В Відносна нестабільність частоти кварцового ген. Похибка вимірювання частоти Електродинамічний логометричний частотомір 36 127 220 __  1.
37727. Программирование на ассемблере MASM32. Изучение среды разработки RADasm и отладчика OllyDbg 584.5 KB
  Они необходимы программе для обработки и хранения в памяти команд и данных а также получения информации о собственном текущем состоянии и состоянии процессора.1: пространство адресуемой памяти до 2х в 32й степени байт 4 Гбайт для Pentium II и выше до 2х в 36 степени байт 64 Гбайт; регистры для хранения данных общего назначения; сегментные регистры; регистры состояния и управления; регистры устройства вычислений с плавающей запятой сопроцессора; набор регистров целочисленного MMXрасширения отображенных на регистры...
37728. Исследование линейных электрических цепей постоянного тока 309.11 KB
  1 ток в цепи и падения напряжения на участках цепи определяются по закону Ома: Разветвленная цепь с одним источником э. Сущность метода наложения основывается на принципе суперпозиции заключающегося в том что ток в отдельной ветви линейной разветвленной цепи равен алгебраической сумме...
37729. ИССЛЕДОВАНИЕ РАЗВЕТВЛЕНОЙ ЛИНЕЙНОЙ ЭЛЕКТРИЧЕСКОЙ ЦЕПИ ПОСТОЯННОГО ТОКА 48 KB
  1 за точные то абсолютная погрешность метода эквивалентного генератора таб.4 по сравнению с этими данными для тока I3 составляет 14 мА а абсолютная погрешность при использовании принципа наложения таб.3 мА так как данный ток будет течь в противоположную сторону по сравнении с указанным на схеме при включенном Е2 абсолютная погрешность составляет 34. Таким образом общая абсолютная погрешность для тока I3 составит 3.
37730. Изучение законов равноускоренного движения 232 KB
  Цель работы: изучение динамики поступательного движения связанной системы тел с учетом силы трения; оценка силы трения как источника систематической погрешности при определении ускорения свободного падения на лабораторной установке. Ускорение свободного падения можно найти с помощью простого опыта: бросить тело с известной высоты и измерить время падения я затем из формулы вычислить . Основная задача которая стоит перед экспериментатором при определении ускорения свободного падения описываемым методом состоит в выборе оптимального...
37731. Определение средней длинны свободного пробега и эффективного диаметра молекул воздуха 137.5 KB
  Краткое теоретическое обоснование методики измерений Основное уравнение динамики твёрдого тела вращающегося вокруг неподвижной оси имеет вид: 1 Где момент импульса вращающегося тела; момент его инерции относительно оси вращения; угловая скорость вращения и момент силы....