4874

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

Лекция

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

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

Русский

2012-11-28

48.5 KB

105 чел.

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

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

индексы

значения


 

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

42962. Демпфер тангажа 4.18 MB
  Демпфери й автомати стійкості, як окремі (автономні) прилади, використовуються тільки на літаках другого покоління. На сучасних літаках вони або поєднуються в окремі комплексні системи керованості й стійкості, або входять до складу систем автоматичного керування й включаються в роботу при переході САУ в режим демпфірування (режим спільного штурвального керування).
42963. Технологический процесс ремонта и испытания тормозной рычажной передачи грузового вагона 547.88 KB
  Назначение и конструкция тормозной рычажной передачи грузового вагона.20 Реферат Данная курсовая работа посвящена изучению технологического процесса ремонта тормозной рычажной передачи грузового вагона. 1 Назначение и конструкция тормозной рычажной передачи грузового вагона Рычажной тормозной передачей называется система тяг и рычагов посредством которых усилие человека при ручном торможении или усилие развиваемое сжатым воздухом по штоку тормозного цилиндра при...
42964. Исчисления экономических показателей работы предприятия и его подразделений 72.38 KB
  Введение Во введении студент должен охарактеризовать значение электроустановок в трубных и других цехах. Таблица Сметная стоимость оборудования Наименование электрооборудования Мощность кВт Количество шт Сметная стоимость руб.5 Определяем транспортные расходы: Тр = 01 · Ссм где Тр транспортные расходы руб.6 Определяем заготовительноскладские...
42965. Разработка информационной системы по предметной области спортивный комплекс 505.53 KB
  Информационнопоисковая система это система обеспечивающая поиск и отбор необходимых данных в специальной базе с описаниями источников информации индексе на основе информационнопоискового языка и соответствующих правил поиска.0 располагающей широкими возможностями по созданию приложений баз данных необходимым набором драйверов для доступа к самым известным форматам баз данных удобными и развитыми средствами для доступа к информации расположенной как на локальном диске так и на удаленном сервере а также большим коллекцией...
42966. Цифровая радиолиния КИМ-ЧМнФМ 4.95 MB
  Рязань 2012 Содержание Общая характеристика системы управления Расчет и выбор основных технических характеристик системы 2.5 Расчет энергетического потенциала 3Контур управления и его анализ 4Разработка функциональной схемы радиолинии Спектр сигнала КИМЧМнФМ Описание функциональной схемы передатчика Описание функциональной схемы приемника Конструкция бортового приемника Заключение Литература 1. Общая характеристика системы управления сигнал дискретизация квантование кодирование приемник Командное радиоуправление...
42967. КОМПЬЮТЕРНОЕ ПРОЕКТИРОВАНИЕ МИКРОВОЛНОВОГО ФИЛЬТРА НИЖНИХ ЧАСТОТ НА ОСНОВЕ МИКРОПОЛОСКОВОЙ ЛИНИИ 107.64 KB
  Целью работы является проектирование фильтра нижних частот на основе микрополосковой линии определение продольных и поперечных величин всех его элементов. Основной задачей будет нахождение наиболее оптимальной модели фильтра...
42968. Расчет оборудования для вакуум-кристаллизации галургического хлорида калия на БКПРУ- 1.03 MB
  Для охлаждения осветленного насыщенного щелока от 90 до 18–°C используется принцип самоиспарения, при котором испарение части растворителя – воды и охлаждение щелока достигается в результате кипения щелока под вакуумом. При этом растворный пар образуется за счет тепла самого щелока, температура которого понижается.
42969. Доходы и расходы организации 605.54 KB
  Новосибирск Проверил: преподаватель кафедры ЭУЗ Ершова Татьяна Валентиновна Новосибирск 2010 План курсовой работы: План курсовой работы Доходы организации общие положения Доходы от обычных видов деятельности Операционные доходы...
42970. Расчет оборудования для вакуум-кристаллизации галургического хлорида калия на БКПРУ-4 1.03 MB
  Количество испаренной воды в каждой ступени рассчитываем по уравнению теплового баланса где Gn–количество щелока поступающего в nую ступень ВКУ кг ч; Сщел –теплоемкость щелока кДж кгС; tн –tк –перепад температур в nой ступени ВКУ С; rn –удельная теплота парообразования на nой ступени ВКУ кДж кг. Сводная таблица материального баланса Состав Приход кг ч Расход кг ч KCl раствор 8455216 3578556 KCl твердый 487666 NCl раствор 7241179 7241179 NCl твердый H2O раствор 27354605 24168545 H2O испаренная ...