Конспект лекций по программированию для начинающих. Гладков В.П. - 171 стр.

UptoLike

ВУЗ: 

ПНИПУ | Пермь

Составители: 

Рубрика: 

173
начальная граница поиска L=1, конечная граница поиска R=7;
середина части поиска i=(L+R) div 2 = 4;
поскольку B[4]=6<a=7, то отбрасываем левую часть: L=i+1=5, R=7.
Третий шаг поиска:
номер элемента: 5 6 7;
массив B={ 7,10,12 };
начальная граница поиска L=5, конечная граница поиска R=7;
середина части поиска i=(L+R) div 2 = 6;
поскольку B[6]=10>a=7, то отбрасываем правую часть: L=5, R=i-1=5.
Четвертый шаг поиска:
номер элемента: 5;
массив B={ 7 };
начальная граница поиска L=5,
конечная граница поиска R=5;
середина части поиска i=(L+R) div 2 = 5;
поскольку B[5]=7=a=7, то искомый элемент найден в позиции 5.
Фрагмент программы на Паскале, реализующий двоичный поиск, приведен
ниже:
l:=1; r:=n;
f:=false; {не найдено}
while (l<=r) and not f do
begin i:=(l+r) div 2;
if b[i]=a then f:=true {нашли}
else if b[i]<a then l:=i+1 else r:=i-1
end.
Тестирование.
Тест 1: a=7, n=15, b={1,3,5,7,9,10,12,14,16,18,21,23,25,27,29}.
Ответ: искомый элемент найден в позиции 4.
Тест 2: a=6, n=15, b={1,3,5,7,9,10,12,14,16,18,21,23,25,27,29}.
Ответ: искомый элемент не найден.
11.7. Сортировка массивов
Для применения двоичного поиска массив должен быть отсортирован, т.е.
элементы массива должны быть переставлены в порядке возрастания или убывания
значений элементов. При решении задачи сортировки обычно выдвигается
требование минимального использования дополнительной памяти, что исключает
применение дополнительных массивов. Эффективность алгоритмов сортировки
оценивается числами: С - количество необходимых сравнений элементов, М -
количество
пересылок элементов. Они определяются некоторыми функциями от
числа n сортируемых элементов. Здесь рассматриваются простые методы
сортировки, которые требуют порядка n
2
сравнений. Их использование
обусловлено следующими причинам:
1) простые методы хорошо подходят для разъяснения свойств большинства
принципов сортировки; 
                                    173

     начальная граница поиска L=1, конечная граница поиска R=7;
     середина части поиска i=(L+R) div 2 = 4;
     поскольку B[4]=6a=7, то отбрасываем правую часть: L=5, R=i-1=5.
   Четвертый шаг поиска:
      номер элемента: 5;
      массив B={ 7 };
      начальная граница поиска L=5, конечная граница поиска R=5;
      середина части поиска i=(L+R) div 2 = 5;
      поскольку B[5]=7=a=7, то искомый элемент найден в позиции 5.
   Фрагмент программы на Паскале, реализующий двоичный поиск, приведен
ниже:
   l:=1; r:=n;
   f:=false; {не найдено}
   while (l<=r) and not f do
   begin      i:=(l+r) div 2;
              if b[i]=a then f:=true {нашли}
              else if b[i]

Страницы