4874

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

Лекция

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

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

Русский

2012-11-28

48.5 KB

109 чел.

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

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

индексы

значения


 

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

26094. Глобализация 29.47 KB
  Если считать ее древним явлением то глобализация всемирноисторический процесс. Глобализация сравнительно новый термин получивший в последнее десятилетие распространение в научной и политической литературе. Предметом оживленных дебатов служит буквально все что такое глобализация когда она началась как она соотносится с другими процессами в общественной жизни каковы ее ближайшие и отдаленные последствия.
26095. Модернизация 25.09 KB
  Сегодня понятие модернизации рассматривается преимущественно в трех различных значениях: 1 как внутреннее развитие стран Западной Европы и Северной Америки относящееся к европейскому Новому времени; 2 догоняющая модернизация которую практикуют страны не относящиеся к странам первой группы но стремящиеся их догнать; 3 процессы эволюционного развития наиболее модернизированных обществ Западная Европа и Северная Америка т. модернизация как некий перманентный процесс осуществляющийся посредством проведения реформ и инноваций что...
26096. Человек в современной культуре. Культурная модернизация 18.66 KB
  Формирование личности в современных условиях: рост независимости от власти традиционных факторов как семья религия; открытость новой практике и в отношениях с людьми; вера в могущество науки и отказ от пассивности и фатализма; стремление индивида к повышению образовательного и профессионального статуса; возрастание интереса к социальной и политической жизни и активное участие в ней; долгосрочное планирование дел и действий стремление к точности во времени. Проблема идентичности Проблема идентичности тесно связана с темой субъекта...
26097. Культурология как наука: междисциплинарные связи, предмет, объект, содержательная область и проблемные поля, структура 19.48 KB
  Лесли Элвин Уайт Открытие культуры когданибудь встанет в истории науки в один ряд с гелиоцентрической теорией Коперника или открытием клеточной основы всех форм жизни. проясняет природу и смыслы культуры раскрывает ее роль в общественной жизни А. помогает прояснить то подлинное значение культуры которое присутствует в трудах выдающихся мыслителей как прошлого так и настоящего вскрывает причины искажений в их теоретических позициях С. предлагает иную интерпретацию взаимоотношений культуры и природы которая коренным образом...
26098. Происхождения термина 21.88 KB
  написал трактат о земледелии перевод названия которого по латыни звучит примерно так: агрокультура. Отсюда первоначально слово культура применялось как агротехнический термин обработка земли возделывание почвы. В значении самостоятельного понятие культура появилось в трудах немецкого юриста С.
26099. Философские и научные основания постижения культуры 13.42 KB
  Имеет смысл лишь в границах определенной культуры философские идеи свойством культурной уникальности и самобытности философ же пытается постичь его в прямой и непосредственной связи с человеческой субъективностью всегда культурно обусловленной Смотреть философскими глазами на мир значит смотреть на него как на мир культуры своей культуры видеть в нем отражение собственной исторически и общественно сформированной индивидуальности. Восприятие через призму культуры философия как знание о мире не выходит за культурный горизонт своей...
26100. Культура как система 20.17 KB
  Однако такое восприятие культуры утвердилось далеко не сразу. Начало системному рассмотрению культуры было положено Эдуардом Бернеттом Тайлором в работе Первобытная культура. На основе изучения большого этнографического материала автор описывает и анализирует конкретные элементы первобытной культуры на фоне культуры мировой и формулирует целостное видение культуры первобытности в контексте теории анимизма специфической веры первобытного человека в одушевленность всей природы которая связывала в единую целостность весь его практический...
26101. Методология, методы и методика исследования культуры 13.43 KB
  Методология система базовых мировоззренческих принципов исследования включающая методы методики способы и средства реализации поставленных целей и задач. Методология исследования культуры: Феноменологические Функционализм Структурализм Постструктурализм Системный Синергетический Постмодернизм Диалектический Семиотический Органицизм Диффузионизм Цивилизационный Аксиологический и др. Методология: Универсалистская Индивидуалистическая Конструктивистская Метод последовательность шагов действий которые необходимо...
26102. Основные подходы в изучении культуры 17.67 KB
  Ценности нормы и значения Предметные и организационные формы Главная функция Креативная творение бытия человеком или для человека Адаптация и воспроизводство жизненною уклада людей Латентность поддержание образца и социализация Воспроизводство и обновление самой деятельности Приоритетный метод исследования Диалектический Эволюционный Структурнофункциональный Системнодеятельностный Философский подход дает самую широкую панораму видения культуры предполагая изучение фундаментальных оснований человеческого бытия глубин самосознания...