4874

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

Лекция

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

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

Русский

2012-11-28

48.5 KB

104 чел.

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

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

индексы

значения


 

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

65733. ФУНКЦІЇ ОРГАНІВ ДОСУДОВОГО СЛІДСТВА В КРИМІНАЛЬНОМУ ПРОЦЕСІ УКРАЇНИ 182 KB
  У науці кримінального процесу концепція щодо визначення кримінальнопроцесуальних функцій має більш як сторічну історію. Це пояснюється насамперед тим що правильне визначення кримінально-процесуальних функцій та їх...
65734. Активізація залучення прямих іноземних інвестицій в економіку України в умовах глобальної конкуренції 265.5 KB
  В умовах глобальної конкуренції роль прямих іноземних інвестицій ПІІ полягає в залученні не лише необхідних обсягів капіталу а й сучасних технологій методів управління та висококваліфікованих менеджерів. Разом з тим глобалізація світогосподарських взаємин за участю прямих іноземних інвестицій...
65735. Удосконалення розрахунку напружено-деформованого стану мостових конструкцій з урахуванням динамічного впливу вантажних поїздів 697.5 KB
  Штучні споруди є невід’ємною та важливою складовою транспортної системи країни однак до цього часу в Україні відсутні рекомендації з визначення швидкісних режимів руху поїздів мостами. Більш ніж 10 залізничних мостів в Україні внаслідок наявності дефектів є бар’єрними об’єктами що призводить...
65736. ЖАНРОВІ МОДИФІКАЦІЇ В ПОЕЗІЇ В. СКОТТА ТА ПОЕТІВ-«ЛЕЙКІСТІВ» 139.5 KB
  Скотта і поетів лейкістів яких об’єднували схожі світоглядні позиції та напрямки естетичних пошуків ще недостатньо повно висвітлені в науці особливо в аспекті засвоєння народних традицій що вплинули на картину світу британського романтизму на його ранньому етапі й зумовили подальші художні відкриття.
65737. МОДЕЛЮВАННЯ І ПРОГНОЗУВАННЯ ДІЇ НЮХОВОГО НАНОБІОСЕНСОРА НА ОСНОВІ МОЛЕКУЛИ БІЛКА ТИПУ GPCR 481.5 KB
  Причинами цього є поперше те що сучасна кремнієва електроніка досягає межі мініатюризації і для виведення її на якісно новий рівень розвитку створення так званого квантового комп'ютера необхідна нова фізична елементна база з елементами розміру порядку нанометра тобто розміру молекули.
65738. Робота та розрахунок сталевих нагельних з’єднань дерев’яних конструкцій за повторних навантажень 1.33 MB
  Велике значення мають дослідження міцнісних і деформативних характеристик нагельних з'єднань дерев'яних елементів при одноразових та повторних навантаженнях оскільки при експлуатації значна кількість дерев'яних конструкцій знаходяться саме в таких умовах.
65739. ПРАВОВЕ РЕГУЛЮВАННЯ ПРОТИДІЇ ІНФОРМАЦІЙНИМ ВІЙНАМ В УКРАЇНІ 155.5 KB
  Незважаючи на надзвичайну важливість забезпечення належного функціонування всіх сфер життєдіяльності людини суспільства та держави необхідність ефективного забезпечення інформаційної безпеки держави зокрема шляхом вироблення надійного механізму протидії інформаційним війнам...
65740. СТАН АНТИОКСИДАНТНОЇ СИСТЕМИ ТА НЕСПЕЦИФІЧНА РЕЗИСТЕНТНІСТЬ У ТВАРИН ЗА ДІЇ ПРОБІОТИКІВ БПС 44 ТА БПС Л 227.5 KB
  Мета роботи: зясувати вплив пробіотичних препаратів БПС44 та БПСЛ на стан антиоксидантної системи та неспецифічну резистентність молодняку великої рогатої худоби ВРХ та свиней; встановити фактори антагоністичної дії штамів бактерій компонентів пробіотиків.
65741. ЗАБЕЗПЕЧЕННЯ ЯКОСТІ ПОСЛУГ ПЕРЕДАЧІ МУЛЬТИМЕДІА МЕРЕЖАМИ НОВОГО ПОКОЛІННЯ 1.25 MB
  Даний процес може сприяти виникненню проблем які пов’язані із гарантуванням рівня якості обслуговування мереж передачі мультимедійної інформації. Передплатники цих систем передачі мультимедійної інформації вимагають надання нових послуг які можуть бути доступними в будь якому місці...