План лекції
- Пошукові алгоритми
- Лінійний пошук
- Бінарний пошук
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].
Контрольні питання:
- Поняття пошукових алгоритмів.
- Принцип роботи лінійного пошуку.
- Принцип роботи бінарного пошуку.
