Лекція №8 Пошук

План лекції

  1. Пошукові алгоритми
  2. Лінійний пошук
  3. Бінарний пошук

1 Пошукові алгоритми

Пошук необхідної інформації – це одна з фундаментальних задач теоретичної інформатики та програмування. Саме пошукові алгоритми найчастіше є фрагментами різноманітних більш складних алгоритмів. Пошуковими алгоритмами називають алгоритми, що здійснюють пошук потрібної інформації у множині заданих елементів.

2 Лінійний пошук

Найчастіше треба відшукати інформацію у невідсортованій послідовності елементів. У цьому випадку пошук зводиться до послідовного перегляду всіх елементів масиву, поки не знайдемо шуканий елемент. Такий пошук називається лінійним, або послідовним.

Алгоритм такого пошуку матиме такий вигляд:

1. Почнемо перегляд заданого масиву з першого елемента.

2. Поки шуканий елемент х не збігається з поточним елементом масиву a[i] і ми не вийшли за межі заданого масиву, то перейти до наступного елемента в масиві.

3. Якщо при відшуканні елемента х у масиві ми вийшли за його межі, тобто порядковий номер поточного елемента масиву сягнув значення N, то це означає, що шуканий елемент у заданому масиві відсутній. У протилежному випадку шуканий елемент знайдено на i-му місці в масиві.

3 Бінарний пошук (Пошук діленням навпіл)

Пригадаємо, як ми здійснюємо пошук у словнику:
1. Відкриваємо словник у довільному місці й дивимося: якщо шукане слово знайдено, то пошук припиняємо, в іншому випадку переходимо до наступного пункту;
2. Якщо слово знаходиться попереду, то друга частина словника нас уже не цікавить і ми відкриваємо його десь усередині першої частини і починаємо пошук так само, як і в пункті 1);
3. Якщо слово знаходиться далі, то перша частина словника нас не цікавить і ми відкриваємо його десь усередині другої частини та починаємо пошук так само, як і в пункті 1).

Це є алгоритм пошуку інформації в упорядкованій послідовності елементів. Він носить назву бінарного (двійкового) пошуку, або пошуку методом поділу навпіл.

Визначимося щодо нашої задачі в алгоритмічних термінах.

Нам задано масив ai , i=1,2,…,n, для елементів якого справджується умова: ai≤ai+1, i=1,2,…,n-1. Шуканий елемент позначимо x, а елемент масиву, відносно якого масив ділиться на дві частини, – через a[m].

Тепер алгоритм бінарного пошуку виглядатиме так:

1. Визначимо m.

2. Якщо a[m]=x, то пошук завершено і переходимо до п.5, в іншому випадку переходимо до п.3.

3. Якщо a[m]<x, то всі елементи з індексами, меншими за m, можна відкинути і перейти до п.1.

4. Якщо a[m]>x, то всі елементи з індексами, більшими за m, можна відкинути і перейти до п.1.

5. Вивести результат a[m].


Контрольні питання:

  1. Поняття пошукових алгоритмів.
  2. Принцип роботи лінійного пошуку.
  3. Принцип роботи бінарного пошуку.