4874

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

Лекция

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

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

Русский

2012-11-28

48.5 KB

103 чел.

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

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

индексы

значения


 

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

76837. Матка и ее строение 182.07 KB
  При нарушениях процесса срастания зачатков формируются аномалии и пороки развития выражающиеся в образовании седловидной двурогой матки; удвоения шейки матки и влагалища. У новорожденной матки самой длинной 35 см является шейка. К 10 годам общая длина матки равняется 5 см шейка и тело по длине одинаковы. Треугольной формы полость матки переходит в шеечный канал с внутренним и наружным отверстиями в нем.
76838. Маточная труба: строение, отношение к брюшине, кровоснабжение и иннервация 181.1 KB
  Маточная труба туба утерина салпинкс фаллопиева труба имеет длину в 1012 см просвет в 0204 см. Труба имеет маточное и брюшное отверстия и сообщает женскую брюшную полость с полостью матки влагалища и наружной средой. Маточная труба одета брюшиной со всех сторон с образованием брыжейки из прилегающего к трубе отдела широкой маточной связки от которой и зависит подвижность органа.
76840. Женские наружные половые органы, их строение, кровоснабжение, иннервация 182.75 KB
  Наружные половые органы у женщин genitli extern vulv cunnus pudendum muliebre включают лобок большие и малые половые губы клитор преддверие влагалища с вестибулярными железами и луковицей девственную плеву. Они развиваются с 3го месяца из индифферентного полового бугорка мочеполовой борозды половых валиков которые под хромосомным и гормональным влиянием превращаются: половой бугорок в клитор половые валики в малые и большие половые губы мочеполовая борозда в половую щель и преддверие влагалища. Большие половые губы ...
76841. Мышцы и фасции мужской и женской промежности, их кровоснабжение и иннервация 182.78 KB
  Под кожей жировой клетчаткой и поверхностной фасцией располагаются мышцы фасции клетчатка образующие мочеполовую и тазовую диафрагмы седалищнопрямокишечную ямку. Поверхностная и глубокая поперечные мышцы и фасции образуют мышечносухожильный центр промежности натянутый между противоположными седалищными ветвями и буграми. Часть волокон глубокой мышцы входит в состав наружного уретрального сфинктера.
76842. Тазовая брюшина 180.6 KB
  Париетальная брюшина выстилает стенки малого таза изнутри образуя тазовый этаж брюшной полости. Без видимой границы париетальная брюшина переходит в висцеральную покрывающую органы в виде трех анатомических вариантов интраперитонеального со всех сторон мезоперитонеального с трех сторон экстра ретроперитонеального с одной стороны. Между пупком и лобковым симфизом париетальная брюшина образует парные правые и левые складки – медиальную и латеральную пупочные умбиликальные и непарную пупочную срединную.
76843. Общее строение кровеносных сосудов 185.59 KB
  Большой круг начинается восходящей аортой из левого желудочка далее аорта разветвляется на многочисленные артерии переходящие в органах и тканях в микроскопические сосуды из которых формируются вены последовательно они сливаются в верхнюю и нижнюю полую впадающие в правое предсердие где и заканчивается большой круг. Малый легочный круг начинается легочным стволом из правого желудочка ствол распадается на правую и левую легочные артерии которые после многократных разделений внутри легких на уровне ацинуса переходят в микрососуды....
76844. Сединения артерий и вен 179.99 KB
  Межсистемные и внутрисистемные артериальные соединения возникают между артериями головы и шеи между ветвями грудной и брюшной аорты между артериями конечностей. Артериальный круг мозга находится на основании головного мозга и образуется задними мозговыми артериями из базилярной и позвоночных артерий подключичной системы передними и средними мозговыми артериями из внутренней сонной система общих сонных артерий. Вокруг и внутри щитовидной железы образуются межсистемные анастомозы между верхними щитовидными артериями из наружной сонной и...
76845. Подмышечная и плечевая артерии 181.8 KB
  Артерия лежит в подкрыльцовой впадине глубоко и латерально. Аксиллярная артерия условно подразделяется на три отдела: Первый на уровне клавикулопекторального треугольника между ключицей и малой грудной мышцей. В нем начинаются ветви: подлопаточные верхняя грудная к пекторальным мышцам и первым двум межреберным промежуткам; грудоакромиальная артерия к грудиноакромиальному и плечевому суставам подключичной и дельтовидной мышцам большой и малой грудным мышцам.