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;
}
Если известно, что данные в массиве расположены упорядоченно (будем считать, что элементы отсортированы по возрастанию), то можно предложить намного более эффективный способ поиска элементов. Суть метода заключается в том, что после каждой операции сравнения элемента массива с искомым, диапазон поиска сужается по следующим правилам:
Понятно, что начинать поиск удобнее всего с элемента, находящегося в середине массива. Поскольку на каждом шаге поиска диапазон сужается в два раза, нетрудно посчитать, что в худшем случае, для поиска в массиве из 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 | |
Это совокупность основанных на концептуальном представлении о роли и месте культуры в жизни общества организационно управленческих материально технических финансовых информационных кадровых ресурсов и правового обеспечения. В любой стране государственная культурная политика призвана: обеспечить охрану и учет культурного наследия сохранение и преемственность национальнокультурных традиций защиту национальной культуры и языка в мире расширяющихся международных контактов и усиления межконтинентальных и межрегиональных информационных... | |||