ПОШУК ДАНИХ

Пошук даних у векторі і файлі виконується по ключу Як і при сортуванні, виділяють два методи пошуку:внутрішнійізовнішнійУ першому випадку весь файл знаходиться у відведеній під програму памяті ЕОМ У разі зовнішнього пошуку велика частина даних знаходиться в зовнішній памяті, наприклад на жорсткому диску

Розглянемо внутрішній пошук стосовно одномерному масиву

Припустимо, щохце вектор, що міститьпключів Нехайkey  є аргументом пошуку, тобто шуканим значенням ключа Сформулюємо задачу пошуку: встановити в змінну search  найменше ціле число i таке, щоx[i] = key,  якщо такеi існує, і нуль в іншому випадку (При такій постановці завдання нижня межа масиву х повинна бути більше нуля)

921 ПОСЛІДОВНИЙ ПОШУК

Послідовний пошук є найпростішою формою пошуку У представленій формулюванні запис фрагмента пошуку тривіальна:

перем х [20], знайшов, ключ, ин, п

<Будівлю значень вектора х і змінної ключ>

n = 20 знайшов = 0 ін = 1

поки (ін <= п) і (знайшов = 0) цикл якщо х [ін] = ключ тоді

знайшов = ін

КонецЕсли ін = ин +1 конецЦікла / / поки якщо знайшов = 0 тоді

Повідомити (Ключ не найден”) інакше

Повідомити (Бажаємий елемент має у векторі x номер + Рядок (знайшов)) КонецЕсли

Ефективність послідовного пошуку оцінимо з припущення, що аргумент пошуку може равновероятно розташовуватися в будь-якій позиції масиву Підрахуємо середнє число порівнянь виду х [ін] = ключ,необхідних для завершення пошуку Якщо аргумент є першим елементом масиву, то необхідно одне порівняння якщо останнім, то необхідно і порівнянь Тобто середнє число порівнянь для успішного пошуку складе (n + 1) / 2 А в разі неуспішного пУ будь-якому випадку обчислювальна складність алгоритму послідовного пошуку дорівнює 0 (п)

Область застосування послідовного пошуку пошук в невпорядкованих масивах (файлах) Якщо ж дані впорядковані, то слід застосовувати бінарний пошук, що має і іншу назву дихотомія

Джерело: Бартеньев О В 1С: Підприємство: програмування для всіх Базові обєкти та розрахунки на одній дискеті М: Діалог-МІФІ, 2005 464 с

Схожі статті:


Сподобалася стаття? Ви можете залишити відгук або підписатися на RSS , щоб автоматично отримувати інформацію про нові статтях.

Коментарів поки що немає.

Ваш отзыв

Поділ на параграфи відбувається автоматично, адреса електронної пошти ніколи не буде опублікований, допустимий HTML: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

*

*