4874

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

Лекция

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

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

Русский

2012-11-28

48.5 KB

106 чел.

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

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

индексы

значения


 

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

55793. Розвиток процесів сприймання у молодших школярів на уроках природознавства 58 KB
  Для розвитку процесів сприймання варто використовувати спеціальні прийоми вправи завдання. Для розвитку такої чутливості необхідно привчати школярів насамперед прислухатися й розрізняти...
55794. Розвиток розумових та творчих здібностей учнів шляхом використання методів розвиваючого навчання 106 KB
  Головне щоб вони відповідали змісту матеріалу та віку учнів збагачували знання розвивали науковий світогляд мислення практичні вміння а отже й активність.
55795. Розвиток творчих здібностей учнів на уроках інформатики через організацію проектної діяльності 53 KB
  Проектний метод дозволяє реалізувати проблемне навчання що активізує і поглиблююче пізнання дозволяє навчати самостійного мислення і діяльності системному підходу в самоорганізації...
55796. Развитие познавательного интереса учащихся на уроках русского языка 81 KB
  Дети тему урока не знают. Ирис нежный расцветает фикус листья расправляет Есть любовь цветы и дети что всего важней на свете. Или при изучении частиц: Что порадовало б вас...
55797. РОЗВИТОК ТВОРЧИХ ЗДІБНОСТЕЙ УЧНІВ ІЗ ЗВ′ЯЗНОГО МОВЛЕННЯ НА УРОКАХ УКРАЇНСЬКОЇ МОВИ ТА ЛІТЕРАТУРИ 189 KB
  Тоді в той перший мій робочий день серед учнівських оченят я ніби побачила себе бо не одразу змогла розкритися перед учителем не одразу показала на що справді була здатна.
55798. Розвиток особистісного потенціалу учнів на уроках з фізики 256 KB
  Як вчитель допомагаю учням на уроках та в неурочний час оволодіти технологіями життєтворчості прагну створити умови для розкриття внутрішнього потенціалу самооцінки самореалізації самоконтролю учнів...
55799. Розвиток пізнавальної активності в процесі рішення творчих задач 87 KB
  Дуже часто навчання зводиться до розуміння й відтворення прийомів дій типових способів вирішення завдань. Дуже часто при такому аналізі на перший погляд абсурдна ідея перевтілюється й відкриває шлях до вирішення проблеми.
55800. Може, маленька дитина повторює те, що було вже зроблено, створено іншими людьми, але якщо це діяння – плід її власних зусиль, – вона творець; її розумова діяльність – творчість 49 KB
  Щоб сформулювати творчі здібності дитині необхідно якнайбільше вражень про навколишній світ під час виконання різних видів діяльності який їй подобається найбільше а потім в усіх притаманних учням видах діяльності гра малювання конструювання...
55801. РОЗВИТОК КРЕАТИВНОГО МИСЛЕННЯ НА УРОКАХ МАТЕМАТИКИ ТА НАВЧАННЯ ГРАМОТИ 116 KB
  Бо стає важливим не стільки обсяг знань якими володіє людина скільки вміння застосовувати їх у конкретній ситуації. Скільки вовків було у норі Ізза пенька показалось 6 заячих вух. Скільки вух тепер видно Скільки вушок у зайців Скільки крил у горобців