logo

TechCodeview

Алгоритми пошуку

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

Алгоритм пошуку



Зміст

Що таке пошук?

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

Пошук термінології:

Цільовий елемент:

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



Простір пошуку:

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

Складність:

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

Детермінований проти недетермінованого:

Деякі пошукові алгоритми, наприклад двійковий пошук , є детермінованими, тобто дотримуються чіткого систематичного підходу. Інші, такі як лінійний пошук, є недетермінованими, оскільки в гіршому випадку їм може знадобитися перевірити весь простір пошуку.



Важливість пошуку в DSA:

  • Ефективність: Ефективні алгоритми пошуку покращують продуктивність програми.
  • Отримання даних: Швидко знаходити та отримувати певні дані з великих наборів даних.
  • Системи баз даних: Дозволяє швидко надсилати запити до баз даних.
  • Вирішення проблем: Використовується в широкому діапазоні завдань для вирішення проблем.

Застосування пошуку:

Алгоритми пошуку мають численні застосування в різних областях. Ось кілька типових програм:

  • Пошук інформації: Такі пошукові системи, як Google, Bing і Yahoo, використовують складні алгоритми пошуку для отримання відповідної інформації з величезних масивів даних в Інтернеті.
  • Системи баз даних: Пошук є фундаментальним у системах баз даних для отримання конкретних записів даних на основі запитів користувача, покращуючи ефективність пошуку даних.
  • Електронна комерція: Пошук має вирішальне значення на платформах електронної комерції, щоб користувачі могли швидко знаходити продукти на основі своїх уподобань, специфікацій або ключових слів.
  • Мережа: У мережі алгоритми пошуку використовуються для ефективної маршрутизації пакетів через мережі, пошуку оптимальних шляхів і керування мережевими ресурсами.
  • Штучний інтелект: Алгоритми пошуку відіграють важливу роль у додатках штучного інтелекту, таких як вирішення проблем, ігри (наприклад, шахи) і процеси прийняття рішень
  • Розпізнавання образів: Алгоритми пошуку використовуються в завданнях зіставлення шаблонів, таких як розпізнавання зображень, розпізнавання мови та розпізнавання рукописного тексту.

Основи алгоритмів пошуку:

  • Вступ до пошуку – Підручник зі структури даних і алгоритмів
  • Важливість пошуку в структурі даних
  • Яке призначення алгоритму пошуку?

Алгоритми пошуку:

  • Лінійний пошук
  • Лінійний пошук Sentinel
  • Двійковий пошук
  • Мета двійковий пошук | Односторонній бінарний пошук
  • Тернарний пошук
  • Перейти до пошуку
  • Інтерполяційний пошук
  • Експоненціальний пошук
  • Пошук Фібоначчі
  • Повсюдний бінарний пошук

Порівняння між різними алгоритмами пошуку:

  • Лінійний пошук проти бінарного пошуку
  • Інтерполяційний пошук проти бінарного пошуку
  • Чому двійковий пошук має перевагу над тернарним?
  • Чи лінійний пошук Sentinel кращий за звичайний лінійний пошук?

Бібліотечні реалізації алгоритмів пошуку:

  • Функції бінарного пошуку в C++ STL (бінарний_пошук, нижня_межа та верхня межа)
  • Arrays.binarySearch() в Java з прикладами | Набір 1
  • Arrays.binarySearch() в Java з прикладами | Набір 2 (Пошук у підмасиві)
  • Collections.binarySearch() у Java з прикладами

Легкі проблеми з пошуком:

  • Знайти три найбільші елементи в масиві
  • Знайди пропущене число
  • Знайдіть перший повторюваний елемент у масиві цілих чисел
  • Знайдіть пропущене і повторюване число
  • Пошук, вставка та видалення у відсортованому масиві
  • Рахунок 1 у відсортованому двійковому масиві
  • Два елементи, сума яких найближча до нуля
  • Знайдіть пару із заданою різницею
  • k найбільших (або найменших) елементів у масиві
  • K-й найменший елемент у двовимірному масиві, відсортованому по рядках і стовпцях
  • Знайти спільні елементи в трьох відсортованих масивах
  • Стеля в сортованому масиві
  • Поверх у відсортованому масиві
  • Знайти максимальний елемент у масиві, який спочатку зростає, а потім спадає
  • Дано масив розміром n і числом k, знайти всі елементи, які з’являються більше n/k разів

Середні проблеми з пошуком:

  • Знайти всі трійки з нульовою сумою
  • Знайдіть елемент, перед яким усі елементи менші від нього, а після якого всі більші
  • Знайти найбільшу парну суму в несортованому масиві
  • K’-й найменший/найбільший елемент у несортованому масиві
  • Пошук елемента в упорядкованому та повернутому масиві
  • Знайдіть мінімальний елемент у відсортованому та повернутому масиві
  • Знайти піковий елемент
  • Максимум і мінімум масиву з використанням мінімальної кількості порівнянь
  • Знайдіть фіксовану точку в заданому масиві
  • Знайдіть k найчастіших слів у файлі
  • Знайти k найближчих елементів до заданого значення
  • Дано відсортований масив і число x, знайти пару в масиві, сума якої найближча до x
  • Знайдіть найближчу пару з двох відсортованих масивів
  • Знайти три найближчі елементи з заданих трьох відсортованих масивів
  • Двійковий пошук раціональних чисел без використання арифметики з плаваючою комою

Складні проблеми з пошуком:

  • Медіана двох відсортованих масивів
  • Медіана двох відсортованих масивів різного розміру
  • Пошук у майже відсортованому масиві
  • Знайти положення елемента в сортованому масиві нескінченних чисел
  • Дано відсортований і обернений масив, знайдіть, чи є пара із заданою сумою
  • K’-й найменший/найбільший елемент у несортованому масиві | Найгірший варіант лінійного часу
  • K’-й найбільший елемент у потоці
  • Найкращий перший пошук (інформований пошук)

Швидкі посилання:

  • «Практичні завдання» на пошук
  • «Вікторини» з пошуку

Рекомендовано:

  • Вивчіть структуру даних і алгоритми | Підручник DSA