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

индексы

значения


 

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

79478. Тенденции развития инфраструктуры социально-культурной сферы в современных условиях 27.72 KB
  К инфраструктуре социальнокультурной сферы как совокупности материальных организационных финансовоэкономических кадровых информационнометодических и иных условий осуществления социально культурной деятельности на индивидуальном и общественном уровнях обеспечивающих удовлетворение духовных потребностей людей и развитие их творческих потенций относятся: система образования средства массовой информации учреждения искусств театры киностудии филармонии цирки художественнотворческие мастерские любительские студии и т....
79479. Методика удовлетворения и дальнейшего развития информационно-познавательных потребностей средствами социально-культурной деятельности 26.7 KB
  Блюменау предлагает девять сущностей информационной потребности: нужда потребность; нужда потребность в знаниях; потребность в дополнительных знаниях информационная потребность; потребность в объективно необходимой информации; потребность в потенциально необходимой информации; общественная потребность в знаниях; коллективные информационные потребности; нужда в избирательном отношении к воспринимаемым им сигналам то есть информационный интерес метаинформативная потребность 11 49. Современное поколение подростков находится под...
79480. Особенности информационно-методического обеспечения деятельности культурно-досуговых учреждений 25.61 KB
  Методическое обеспечение понимаемое как система управленческих действий нацеленное на создание технологической базы фактически влияет на качество работы и конкурентоспособность фирмы. актуализируется: от того решения что мы будем заменять на новое когда мы будем это делать за какие деньги почему и за какой срок каким способом Зависит реализация принятых решений место положения фирмы на рынке. Чтобы понять каков оптимальный уровень методической базы надо знать: средний уровень рынка возможности предрасположенность фирмы...
79481. Туризм как форма социально-культурной деятельности: специфика и классификация видов 27.89 KB
  Туризм с точки зрения потребителя это СК и досуговая деятельность осущ. Или же туризм отрасль экономики сфера бизнеса и предпринимательства. Туризм временные выезды за пределы постоянного места жительства и работы в культурнопознавательных рекреационнооздоровительных религиозных спортивных и иных целях без занятия оплачиваемой деятельностью в месте временного пребывания. Существуют многочисленные виды и формы туризма которые подразделяются по различным параметрам.
79482. Функции социально-культурной деятельности 26.71 KB
  СКД это обусловленная нравственно-интеллектуальными мотивами общественно целесообразная деятельность по созданию освоению распространению и дальнейшему развитию ценностей культуры. Адаптивно-нормативная освоение формирующихся индивидом основ санитарно-гигиенической культуры культуры речи а также других элементов человеческой жизнедеятельности адаптация к социуму приобретение способностей к самоконтролю саморегулированию поведения Образовательно-развивающая освоение ценностей культуры последовательный процесс социализации и...
79483. Организационные и сценарно-режиссерские особенности подготовки и проведения различных игровых программ 27.65 KB
  Успешное применение игры происходит лишь при соблюдении ряда условий: игра должна несет положительный эмоциональный заряд в самых разнообразных игровых ситуациях; в ней должны быть задействованы все участники мероприятия и осуществляться сменность ролей играющих; она должна предусматривать преодоление определенных трудностей усложняющихся в процессе игры; в игру необходимо вводить элемент состязательности. Сценарий мероприятия должен иметь два аспекта: художественный и психологопедагогический которые программируются не только выстраиваемый...
79484. Основные направления социально-культурной деятельности в условиях информационного общества 27.15 KB
  Теория Информационного общества начала складываться в 6070ые годы XX века в работах Белла Тоффлера Масуды и т. Предпосылками информационного общества являются: Появление языка письменности изобретение печатного станка появление радио и телевидения развитие информационных компьютерных технологий. Термином информационное общество обычно определяют уровникондиции западного общества и его культурносоциальный эволюционные феномены и ориентиры.
79485. Технология бизнес-планирования в социально-культурном проектировании 29.34 KB
  Бизнесплан документ перспективный и составлять его рекомендуется минимум на ряд лет вперед. Основные рекомендации в подготовке бизнесплана это краткость т. бизнесплан должен быть понятен широкому кругу людей а не только специалистам.
79486. Сущность культурной политики: субъекты, направления, механизмы реализации 26.94 KB
  Это совокупность основанных на концептуальном представлении о роли и месте культуры в жизни общества организационно управленческих материально технических финансовых информационных кадровых ресурсов и правового обеспечения. В любой стране государственная культурная политика призвана: обеспечить охрану и учет культурного наследия сохранение и преемственность национальнокультурных традиций защиту национальной культуры и языка в мире расширяющихся международных контактов и усиления межконтинентальных и межрегиональных информационных...