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

индексы

значения


 

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

34772. Истина, ложь, заблуждение. Конкретность истины. Ложь «во спасение». Проблема врачебных ошибок 41.5 KB
  Конкретность истины.В философии понятие истины совпадает с комплексом базовых концепций позволяющих различить достоверное и недостоверное знание по степени его принципиальной возможности согласовываться с действительностью по его самостоятельной противоречивости непротиворечивости а также в рамках разведения полезности и бесполезности эффективности и неэффективности. категория истины обладает двойственной характеристикой. уклонение от истины принимаемое нами за истинное суждение; основывается всегда на неверности по существу самих...
34773. Практика как критерий истины. Абсолютность и относительность практики как критерия истины 43 KB
  Абсолютность и относительность практики как критерия истины К сожалению фактически все попытки решить проблему критерия истины не увенчались успехом. следует выделить две особенности практики как критерия истины: 1. Это достигается в процессе материального воплощения мышления в человеческой практики. С его помощью невозможно доказать немедленно непосредственно истинность или ложность тех или иных научных теорий которые выходят за пределы возможностей самой практики обусловленной историческим отрезком времени.
34774. Практика как специфический способ отношения человека к миру. Формы практической деятельности. Специфика медицинской практики 34 KB
  Формы практической деятельности. Интегративные функции практики по отношению к другим формам жизнедеятельности В сфере реального отношения людей к миру к природе к обществу к другим людям формируются исходные стимулы развитии всех форм человеческой культуры. Создаваемые в культуре и в материальном производстве и в регуляции отношений между людьми в обществе и наконец в сфере науки искусства философии способы деятельности возникают но сути своей как ответ па определенные проблемы и задачи связанные с воспроизводством...
34775. Глобальные проблемы современности. Философский анализ и решение. Альтернативы будущего 42.5 KB
  Остановим внимание на названных и в первую очередь на экологической проблеме в силу тех причин что все происходящее на планете Земля с участием человека или без него протекает и в природе. Геосфера поверхность Земли как необитаемая так и пригодная для жизни человека. Ноосфера ноо разум область разумной деятельности человека онрделяемая в конечном счете уровнем человеческого интеллекта и объемом перерабатываемой его мозгом информации. С целью их разгадки все сферы взаимоотношений природы и человека были условно разделены на...
34776. Философия медицины. Антропоцентризм. Духовность и медицина. Проблема человека 42.5 KB
  Это касается и права индивида на свободный личный выбор жизни или смерти. Антропоцентризм предписывает противопоставлять феномен человека всем прочим феноменам жизни и Вселенной вообще. Лежит в основе потребительского отношения к природе оправдания уничтожения и эксплуатации других форм жизни. Понимание основ духовной жизни пациента часто включает в себя и знание его духовного развития.
34777. Этический рационализм Сократа. Учение о душе и добродетели. Переоценка ценностей. Особенности метода субъективной диалектики 30 KB
  Сократ около 470 399 до н. Универсальное основание мироздания по Сократу выступает как его всеобщая объективная родовая сущность которая может быть рациональнологически выражена в определенных закономерностях происходящего. Нравственный лучший тот кто знает что именно есть добродетель ибо по Сократу знающий благо поступает в соответствии с этим знанием.
34778. Принцип системности. Система, элемент, структура. Часть и целое, принцип целостности 45 KB
  Органичные системы проходят в процессе их развитии последовательные этапы усложнения и дифференциации. В зависимости от характера отношений со средой различают такие типы поведения систем как реактивное определяемое преимущественно средой адаптивное определяемое средой и функцией саморегуляции присущей самой системе активное в котором существенную роль играют собствен тле цели системы преобразование среды в соответствии с потребностями системы. Наиболее высокоорганизованными являются самоорганизующиеся системы адаптирующиеся и...
34779. Предмет философии и его особенности. Место и роль философии в системе культуры 36.5 KB
  ФИЛОСОФИЯ И КУЛЬТУРА Культура совокупность проявлений жизни творчества и достижений народа или группы народов. По своему содержанию культура расслаивается на самые разные области и сферы: нравы и обычаи; язык и письменность; характер одежды поселений работы; постановка воспитания; экономика; военное дело; политическое и государственное устройство; наука; техника; искусство; религия; все формы проявления объективного духа. Слово культура как научный термин стало употребляться в эпоху Просвещения со второй половины XVII в. В эпоху...
34780. Структура и основные функции философии. Мировоззренческая и методологическая функция 29.5 KB
  Мировоззренческая и методологическая функция ПРЕДМЕТ ФИЛОСОФИИ Философия от греч. Цель философии увлечь человека высшими идеалами вывести его из сферы обыденности придать его жизни истинный смысл открыть путь к самым совершенным ценностям. историю философии.