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

индексы

значения


 

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

17194. КРИЗИС БЕЗБОЖИЯ 68 KB
  И.Ильин КРИЗИС БЕЗБОЖИЯ Первая глава лекции прочитанной И.А. Ильиным в Риге 11 октября 1935 года. Историческое время выпавшее нам на долю исполнено великого и глубокого значения: это эпоха чрезвычайной насыщенности напряженности эпоха крушения подводящего...
17195. ПРЕДАНИЕ И ПРЕДАНИЯ 66.5 KB
  Лосский ПРЕДАНИЕ И ПРЕДАНИЯ Предание ParadosisTraditio один из терминов у которого так много значений что он рискует вовсе утерять свой первоначальный смысл. И это не только по причине некоторого обмирщения которое обесценило столько слов богословского словаря как дух...
17196. ТИПЫ РЕЛИГИОЗНОЙ ЖИЗНИ 96 KB
  Мать МАРИЯ Скобцова ТИПЫ РЕЛИГИОЗНОЙ ЖИЗНИ Если мы начнем изучать историческое место на котором мы находимся или вернее те исторические типы благочестия которые сейчас выработало наше историческое положение то мы сможем объективно и беспристрастно увидеть разн
17197. СПАСЕHИЕ И ОПРАВДАHИЕ 104 KB
  Аpхиепископ Михаил Мудьюгин СПАСЕHИЕ И ОПРАВДАHИЕ Опыт кpаткого pаскpытия пpавославной субъективной сотеpиологии Стpемление к спасению в будущей или загpобной жизни явление хаpактеpизующее духовную жизнь многих веpоятно даже большинства сознательных хpистиан. ...
17198. Замечания по поводу атеистической литературы последних лет 69 KB
  Замечания по поводуатеистической литературы последних лет. Внимательное ознакомление с весьма многочисленной антирелигиозной литературой привело меня к следующим выводам: 1. Эта литература поражает прежде всего своей невероятной отсталостью. В ней можно найти множ...
17199. О детском крещении 41 KB
  О детском крещении Что написано в Священном Писании о крещении Посмотрим основные места. 1 Мф.28:1920 Итак идите научите ВСЕ НАРОДЫ крестя их во имя Отца и Сына и Святого Духа уча их соблюдать все что Я повелел вам; и се Я с вами до скончани
17200. ПРАВОСЛАВНЫЙ ИНТЕРНЕТ В РОССИИ 114 KB
  ПРАВОСЛАВНЫЙ ИНТЕРНЕТ В РОССИИ СОДЕРЖАНИЕ: КАКИМ БУДЕТ ПРАВОСЛАВНЫЙ ИНТЕРНЕТ Москва 7 сентября Метафрасис Первая конференция посвященная перспективам развития православных ресурсов на русском языке в глобальной компьют...
17201. ПРАВОСЛАВИЕ В НОВЕЙШИХ ПЛЮРАЛИСТИЧЕСКИХ ОБЩЕСТВАХ 37.5 KB
  протопресвитер Фома Хопко ректор Св.Владимирской духовной семинарии НьюЙорк ПРАВОСЛАВИЕ В НОВЕЙШИХ ПЛЮРАЛИСТИЧЕСКИХ ОБЩЕСТВАХ доклад на Межправославной подготовнтельной консультации по Всемирной миссии и евангелизму Аддис Абеба январь 1996 г. Перевод с а
17202. Изучение способов и режимов хранения кукурузы 272.5 KB
  Рассмотреть ботанико-биологические особенности кукурузы; изучить типы хранилищ, используемых для хранения кукурузы; проанализировать аспекты поддержки микроклимата при хранении культуры; рассмотреть базовое оборудование хранилищ; провести расчеты вместимости хранилищ и норму убыли при хранении.