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

индексы

значения


 

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

20534. Создание, дополнение и чтение файла данных 80 KB
  Создать файл данных со следующей структурой: шифр товара наименование план выпуска на каждый квартал фактический выпуск в каждом квартале. выпуск Факт. выпуск План. выпуск Факт.
20535. Обработка файла данных 23.5 KB
  Данные по машинам автобазы: номер марка план перевозок факт. Макет исходных данных номер марка план факт о 367 нр ГАЗ 105 100 л 577 ор ЗИЛ 185 185 н 705 ар КамАЗ 220 220 в 368 еу ЛИАЗ 343 340 а 859 ср МАЗ 368 368 у 364 ар УАЗ 373 373 м 290 ао КамАЗ 288 287 н 390 ал ГАЗ 100 99 Алгоритм программы Программа по разработанному алгоритму Командный файл Обработка файла данных CLEAR {Очистка экрана} SET TALK OFF {Команда запрета выполнения отдельных команд} USE Imfd...
20536. Изучение принципов микропрограммного управления 23 KB
  Владимир 2000 Цель работы: Изучение принципов построения микропрограммного устройства управления. Развитие методов параллельной обработки данных и параллельного программирования показало что сложные алгоритмы могут быть эффективно реализованы при микропрограммном управлении что обусловило применение принципов микропрограммного управления в ЭВМ высокой производительности. Микропрограммный принцип управления обеспечивает реализацию одной машинной команды путем выполнения микрокоманд записанных в постоянной памяти.
20537. КЭШ память с прямым распределением 32 KB
  Владимир 2000 Цель работы: Изучение принципа построения кэшпамяти с пря мым распределением. Введение Кэшпамять это быстродействующая память расположенная между центральным процессором и основной памятью. В больших универсальных ЭВМ основная память которых имеет емкость порядка 3264 Мбайт обычно используется кэшпамять емкость 64256 Кбайт т.
20539. Уравнение Беллмана для непрерывных процессов 92.5 KB
  Разобьем этот интервал на 2 интервала Рис Где бесконечно малая величена Запишем уравнение 3 на этих 2х отрезках Используя принцип оптимальности: 4 Обозначим через Подставив в 4 Поскольку значение от выбора управления не зависит то ее можем внести под знак минимума и тогда выражение 5 Разделим каждое слагаемое этого уровня на Перейдем к приделу при На основании теоремы о среднем значении интеграла на бесконечно малом отрезке времени Пояснение Рисунок Тогда 5а 6 полная производная этой функции. Вместо Полученное...
20540. Многокритериальные задачи теории принятия решений 31.5 KB
  Проблему решения оптимизационных задач с учетом множества показателей эффективности называют проблемой решения многокритериальных задач или проблемой векторной оптимизации. Формулировка проблемы оптимизации по векторному критерию была в первые сформулирована Вильфредо Парето 1896г. Таким образом проблема векторной оптимизации это проблема принятия компромиссного решения. В настоящие время можно выделить 4 подхода к основной проблеме векторной оптимизации: т.
20541. Множество решений, оптимальных по Парето 153 KB
  Пусть задача принятия решения состоит в максимизации двух противоречивых и не сводимых друг к другу. Кривая АВ определяет для рассматриваемого примера область Парето которая характеризуется тем свойством что любое принадлежащий этой области решения нельзя улучшить одновременно по всем скалярным критерием. Действительно выбрав произвольно точку М в допустимой области решения не лежащую на кривой АВ не трудно убедится что определяемая ее решению можно улучшить по критерию в точке и максимум в точке достигает максимума. Из сказанного...
20542. Основная задача управления 36.5 KB
  Пусть компоненты управления u представляют собой кусочнонепрерывные функции времени с конечным числом точек разрыва или параметрами. Значение вектора управления u принадлежат заданой допустимой области U uU границы которой могут быть функции времени. Задача определения управления гарантирующего выполнения ограничения1 является типичной задачей управления которую назовем ОЗУосновная задача управления.