Розуміння алгоритмів пошуку в C++: Посібник з лінійного та бінарного пошуку

Searching є основною концепцією в розробці програмного забезпечення. Чи ми шукаємо певне значення в масиві, чи намагаємось знайти запис у базі даних, ефективні алгоритми пошуку є необхідними. У цьому блозі ми розглянемо два базових, але потужних алгоритми пошуку в структурах даних та алгоритмах (DSA): Пошук лінійний та Пошук бінарний.

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

Пошук лінійний

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

Як працює Пошук лінійний?

1. Почати з першого елемента масиву.
2. Порівняти поточний елемент із цільовим значенням.
3. Якщо збіг знайдений, повернути індекс елемента.
4. Якщо не збігається, перейти до наступного елемента.
5. Повторювати кроки 2–4, поки не знайдеться ціль або поки не буде досягнуто кінця масиву.

#include   
using namespace std;  

// Функція для виконання Пошуку лінійного  
int linearSearch(int arr[], int size, int target) {  
 for(int i = 0; i < size; i++) {  
 if(arr[i] == target)  
 return i; // Ціль знайдена на індексі i  
 }  
 return -1; // Ціль не знайдена  
}  

int main() {  
 int data[] = {34, 78, 12, 56, 89, 23};  
 int size = sizeof(data)/sizeof(data[0]);  
 int target = 56;  
 int result = linearSearch(data, size, target);  
 if(result != -1)  
 cout << "Елемент знайдено на індексі " << result << endl;  
 else  
 cout << "Елемент не знайдено в масиві." << endl;  
 return 0;  
}  

// Виведення:  
// Елемент знайдено на індексі 3

Коли використовувати Пошук лінійний

• Невідсортовані дані: Пошук лінійний не вимагає відсортованих даних.
• Малі набори даних: Ефективний для малих масивів, де накладні витрати на складніші алгоритми не є виправданими.
• Простота: Легко реалізується і розуміється, що робить його підходящим для початківців.

Пошук бінарний

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

Як працює Пошук бінарний?

1. Попередня умова: Масив повинен бути відсортований у порядку зростання або спадання.
2. Визначити середній елемент масиву.
3. Порівняти середній елемент із цільовим значенням.

• Якщо збігається, повернути індекс.
• Якщо цільове значення менше, повторити пошук на лівій половині.
• Якщо цільове значення більше, повторити пошук на правій половині.

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

#include   
using namespace std;  

// Функція для виконання Пошуку бінарного  
int binarySearch(int arr[], int size, int target) {  
 int left = 0;  
 int right = size -1;  
 while(left <= right) {  
 int mid = left + (right - left) / 2; // Запобігає можливому переповненню  
 // Перевірити, чи є цільове значення на середньому елементі  
 if(arr[mid] == target)  
 return mid;  
 // Якщо ціль більше, ігноруємо ліву половину  
 if(arr[mid] < target)  
 left = mid + 1;  
 // Якщо ціль менше, ігноруємо праву половину  
 else  
 right = mid - 1;  
 }  
 return -1; // Ціль не знайдена  
}  
int main() {  
 int data[] = {12, 23, 34, 56, 78, 89};  
 int size = sizeof(data)/sizeof(data[0]);  
 int target = 56;  
 int result = binarySearch(data, size, target);  
 if(result != -1)  
 cout << "Елемент знайдено на індексі " << result << endl;  
 else  
 cout << "Елемент не знайдено в масиві." << endl;  
 return 0;  
}  

// Виведення:  
// Елемент знайдено на індексі 3

Коли використовувати Пошук бінарний

• Відсортовані дані: Пошук бінарний вимагає, щоб масив був відсортований.
• Великі набори даних: Надзвичайно ефективний для великих масивів, значно зменшуючи кількість порівнянь.
• Програми з високими вимогами до продуктивності: Ідеально підходить для ситуацій, де продуктивність є пріоритетом, а витрати на сортування (якщо необхідно) є керованими.

Тепер давайте розглянемо кілька завдань з Leetcode, щоб краще зрозуміти вищеописані концепції…

Приклад 1 Пошук у 2D матриці

Вам дається матриця цілих чисел розміру m x n з такими двома властивостями:

• Кожен рядок відсортований в порядку неспадання.
• Перше число в кожному рядку більше за останнє число попереднього рядка.

Дано ціле число target, поверніть true, якщо target є в матриці, або false, якщо його немає.

Приклад 1:

Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3  
Output: true

Приклад 2:

Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13  
Output: false

class Solution{  
public:  
 bool searchMatrix(vector>& matrix, int target){  
 if(matrix.empty() || matrix[0].empty()){  
 return false;  
 }  
 int m = matrix.size();  
 int n = matrix[0].size();  
 int low = 0, high = m * n - 1;  
 while (low <= high){  
 int mid = low + (high - low)/2;  
 int midValue = matrix[mid / n][mid % n];  
 if(target == midValue){  
 return true;  
 }  
 else if(target < midValue){  
 high = mid - 1;  
 }  
 else {  
 low = mid + 1;  
 }  
 }  
 return false;  
 }  
}  

// Часова складність: O(log(m×n))  
// Просторова складність: O(1)

Підхід:

Представлення матриці:

• 2D матриця розміру m x n може бути представлена як 1D масив.
• Для будь-якого індексу i у сплющеній версії матриці, відповідні індекси рядка та стовпця у матриці є:
• Рядок: i / n
• Стовпець: i % n

Пошук бінарний:

• Почати з двох вказівників, low = 0 і high = m * n - 1 (вся матриця розглядається як 1D масив).
• Обчислити індекс середини: mid = low + (high - low) / 2.
• Перевести mid назад до елемента матриці за допомогою: matrix[mid / n][mid % n]
• Порівняти значення в цій позиції з цільовим значенням:

— — →Якщо збігається, повернути true.

— — →Якщо більше, перемістити вказівник high вліво (high = mid - 1).

— — →Якщо менше, перемістити вказівник low вправо (low = mid + 1).
1.
Умова завершення:

• Цикл завершується, коли low > high, що означає, що цільове значення відсутнє в матриці, і функція повертає false.

Покрокове виконання:

matrix = {  
 {1, 3, 5},  
 {7, 10, 11},  
 {12, 15, 20}  
};  
target = 10;

Змінні:

• Розміри: m = 3, n = 3
• low = 0, high = 8 (сплющені індекси від 0 до 8)

Ітерація 1:

• low = 0, high = 8
• mid = 0 + (8 - 0) / 2 = 4
• midValue = matrix[4 / 3][4 % 3] = matrix[1][1] = 10
• Порівняння: 10 == 10
• Результат: Ціль знайдена, повертаємо true

Приклад 2 Коко їсть банани

Коко любить їсти банани. Є n куп бананів, i-та купа містить piles[i] бананів. Охоронці пішли і повернуться через h годин.

Коко може обрати свою швидкість поїдання бананів за годину, яка дорівнює k. Щогодини вона вибирає якусь купу бананів і їсть з неї k бананів. Якщо в купі менше ніж k бананів, вона з’їдає всі банани з цієї купи і не їсть більше бананів протягом цієї години.

Коко любить їсти повільно, але хоче встигнути з’їсти всі банани до того, як охоронці повернуться.

Поверніть мінімальне ціле число k, таке що вона зможе з’їсти всі банани за h годин.

Приклад 1:  
Вхід: piles = [3,6,7,11], h = 8  
Вихід: 4  

Приклад 2:  
Вхід: piles = [30,11,23,4,20], h = 5  
Вихід: 30  

Приклад 3:  
Вхід: piles = [30,11,23,4,20], h = 6  
Вихід: 23

Ключові етапи та логіка

1.
Напишемо допоміжну функцію: ця функція визначає, чи може Коко з’їсти всі банани за h годин при заданій швидкості mid.

Логіка:

Для кожної купи:

• Додаємо piles[i] / mid до total_hours, щоб облікувати повні "порції" бананів, які Коко може з’їсти за годину.
• Якщо є залишок, тобто piles[i] % mid (решта від ділення), Коко потрібно ще одну годину, щоб з’їсти залишкові банани, тому збільшуємо total_hours на 1.

Після обробки всіх куп:

• Якщо total_hours менше або дорівнює h, повертаємо true (швидкості достатньо).
• Інакше повертаємо false.

Застосовуємо Бінарний пошук для мінімізації k, швидкості поїдання.

• Починаємо з start = 1 (мінімальна можлива швидкість).
• Кінцева межа end = max(piles) (максимальний розмір купи, оскільки Коко не може їсти швидше за найбільшу купу).

Процес:

• Обчислюємо середнє значення mid як кандидат на швидкість.
• Використовуємо допоміжну функцію, щоб перевірити, чи дозволяє ця швидкість завершити поїдання за h годин.
• Якщо результат true, зменшуємо діапазон пошуку для пошуку меншої швидкості (end = mid).
• Якщо результат false, збільшуємо діапазон для перевірки більших швидкостей (start = mid + 1).
• Повторюємо, поки діапазон не зійдеться (start == end), після чого start буде мінімальною швидкістю k.

bool possibleHours(vector& piles, int mid, int h) {  
 int total_hours = 0;  
 for (int i = 0; i < piles.size(); i++) {  
 total_hours += piles[i] / mid; // Додаємо години для повних порцій  
 if (piles[i] % mid) { // Додаємо 1 годину для залишків  
 total_hours++;  
 }  
 }  
 return total_hours <= h; // Повертаємо true, якщо години в межах ліміту  
}  

int minEatingSpeed(vector& piles, int h) {  
 int start = 1; // Мінімальна швидкість  
 int end = *max_element(piles.begin(), piles.end()); // Максимальний розмір купи  
 while (start < end) {  
 int mid = start + (end - start) / 2; // Обчислюємо середню швидкість  
 if (possibleHours(piles, mid, h)) {  
 end = mid; // Спробуємо менші швидкості  
 } else {  
 start = mid + 1; // Збільшуємо швидкість  
 }  
 }  
 return start; // Мінімальна швидкість  
}  

// Часова складність: Бінарний пошук: O(log⁡(max розміру купи)) і перевірка годин: O(n)  
// Загальна: O(nlog(max розміру купи))  

// Просторова складність: O(1): Додаткове простір не використовується.

Вхід:

piles = [3, 6, 7, 11], h = 8

Початковий діапазон:

• start = 1, end = 11 (максимальний розмір купи).

Перша ітерація:

• mid = (1 + 11) / 2 = 6.
• Перевіряємо possibleHours(piles, 6, 8):
• Купа 3: ⌈3/6⌉=1 година.
• Купа 6: ⌈6/6⌉=1 година.
• Купа 7: ⌈7/6⌉=2 години.
• Купа 11: ⌈11/6⌉=2 години.
• Загалом = 6 годин (дійсно).
• Оновлюємо end = 6.

Друга ітерація:

• mid = (1 + 6) / 2 = 3.
• Перевіряємо possibleHours(piles, 3, 8):
• Загалом = 10 годин (недійсно).
• Оновлюємо start = 4.

Третя ітерація:

• mid = (4 + 6) / 2 = 5.
• Перевіряємо possibleHours(piles, 5, 8):
• Загалом = 7 годин (дійсно).
• Оновлюємо end = 5.

Четверта ітерація:

• mid = (4 + 5) / 2 = 4.
• Перевіряємо possibleHours(piles, 4, 8):
• Загалом = 8 годин (дійсно).
• Оновлюємо end = 4.

Результат:

• start == end == 4.
• Мінімальна швидкість k = 4

Приклад 3 Знайти мінімум у відсортованому циклічно зсунутому масиві

Нехай є масив довжиною n, відсортований за зростанням, який був циркулювано зсунутим між 1 і n разами. Наприклад, масив nums = [0,1,2,4,5,6,7] може стати:

• [4,5,6,7,0,1,2], якщо його зсунули 4 рази.
• [0,1,2,4,5,6,7], якщо його зсунули 7 разів.

Зверніть увагу, що циркулювання масиву [a[0], a[1], a[2], ..., a[n-1]] на 1 раз дає масив [a[n-1], a[0], a[1], a[2], ..., a[n-2]].

Дано відсортований циклічно зсунутим масив nums з унікальними елементами, поверніть мінімальний елемент цього масиву.

Необхідно написати алгоритм, який працює за час O(log n).

Приклад 1:  
Вхід: nums = [3,4,5,1,2]  
Вихід: 1  
Пояснення: Оригінальний масив був [1,2,3,4,5], зсунений 3 рази.  

Приклад 2:  
Вхід: nums = [4,5,6,7,0,1,2]  
Вихід: 0  
Пояснення: Оригінальний масив був [0,1,2,4,5,6,7] і його зсунули 4 рази.

Приклад 3:  
Вхід: nums = [11,13,15,17]  
Вихід: 11  
Пояснення: Оригінальний масив був [11,13,15,17] і його зсунули 4 рази.  

Обмеження:  
n == nums.length  
1 <= n <= 5000  
-5000 <= nums[i] <= 5000  
Усі елементи nums унікальні.  
nums відсортований і зсунутим між 1 і n разами.

Підхід

Використовуємо підхід бінарного пошуку для знаходження мінімального елемента у відсортованому циклічно зсунутому масиві. Ось розбір:

Крайній випадок: Перевіряємо, чи масив не був зсунутим (nums[left] < nums[right]). Якщо це так, повертаємо nums[left].

Бінарний пошук:

• Використовуємо два покажчики: left (початок масиву) та right (кінець масиву).
• Обчислюємо mid як середній індекс: mid = left + (right - left) / 2.

Перевірка точки повороту:

• Якщо nums[mid] > nums[mid + 1], то точка повороту знаходиться в mid + 1, і ми повертаємо nums[mid + 1] (мінімальний елемент).
• Якщо nums[mid] < nums[mid - 1], то точка повороту знаходиться в mid, і ми повертаємо nums[mid].

Оновлення покажчиків:

• Якщо nums[left] <= nums[mid] (ліва частина відсортована), мінімум має бути праворуч. Оновлюємо left = mid + 1.
• Інакше мінімум знаходиться ліворуч. Оновлюємо right = mid - 1.

Повернення:

• Якщо цикл завершується без явного знаходження точки повороту, повертаємо nums[0] (хоча це не повинно статися для правильного входу).

Підсушування

nums = [4, 5, 6, 7, 0, 1, 2]

Початковий стан

• left = 0, right = 6 (індекси масиву).
• nums = [4, 5, 6, 7, 0, 1, 2].

Крок 1: Перевірка крайнього випадку

• nums[left] = 4, nums[right] = 2. Оскільки 4 > 2, переходимо до бінарного пошуку.

Ітерація 1

• mid = left + (right - left) / 2 = 3.
• nums[mid] = 7.

Перевірка точки повороту:

• nums[mid] > nums[mid + 1] → 7 > 0. Точку повороту знайдено в mid + 1.

Повернення:

• nums[mid + 1] = 0.

Вихід: 0

class Solution {  
public:  
 int findMin(vector& nums) {  
 int left = 0, right = nums.size()-1;  
 // Крайній випадок  
 if(nums[left] < nums[right]){  
 return nums[left];  
 }  
 while(left < right){  
 int mid = left + (right-left)/2;  
 if(nums[mid] > nums[mid+1]) return nums[mid+1];  

 if(nums[mid] < nums[mid-1]) return nums[mid];  
 if(nums[left] < nums[mid]){  
 left = mid+1;  
 }  
 else{  
 right = mid -1 ;  
 }  
 }  
 return nums[0];  
 }  
};

Приклад 4 Пошук у відсортованому циклічно зсунутому масиві

Маємо масив цілих чисел nums, відсортований за зростанням (зі унікальними значеннями).

Перед тим як передати масив до вашої функції, nums може бути зсунутим в невідомій точці повороту k (1 <= k < nums.length), так що результативний масив виглядає так: [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]] (0-індексований). Наприклад, [0,1,2,4,5,6,7] може бути зсунутим в точці повороту 3, ставши [4,5,6,7,0,1,2].

Дано масив nums після можливого зсуву і ціле число target, поверніть індекс target, якщо він є в nums, або -1, якщо його немає в nums.

Необхідно написати алгоритм з часовою складністю O(log n).

Приклад 1:  
Вхід: nums = [4,5,6,7,0,1,2], target = 0  
Вихід: 4  

Приклад 2:  
Вхід: nums = [4,5,6,7,0,1,2], target = 3  
Вихід: -1  

Приклад 3:  
Вхід: nums = [1], target = 0  
Вихід: -1

Масив відсортований, але зсунутим навколо точки повороту, що ускладнює застосування стандартного бінарного пошуку.
Отже, зберігаючи принципи бінарного пошуку, визначимо відсортований підмасив.

Основи бінарного пошуку:

• Використовуємо два покажчики (left та right), щоб виконати бінарний пошук.
• Обчислюємо середній індекс: mid = left + (right - left) / 2.

Визначення відсортованого підмасиву:

• Перевіряємо, яка частина масиву відсортована:
• Якщо nums[mid] >= nums[left], то ліва частина (від left до mid) відсортована.
• Інакше, права частина (від mid до right) відсортована.

Коригування діапазону пошуку:

• Якщо цільове значення знаходиться в відсортованій частині, звужуємо пошук до цього діапазону.
• В іншому випадку шукаємо в не відсортованій частині.

Повернення результату:

• Якщо target знайдено, повертаємо його індекс.
• Якщо цикл завершується без знаходження цілі, повертаємо -1.

class Solution {  
public:  
 int search(vector& nums, int target) {  
 int n = nums.size();  
 int left = 0, right = n-1;  
 while(left <= right){  
 int mid = left + (right - left)/2;  
 if(nums[mid] == target){  
 return mid;  
 }  
 else if (nums[mid] >= nums[left]){  
 //якщо це вірно, то всі числа відсортовані за зростанням  
 if(nums[left] <= target && target <= nums[mid]){  
 right = mid-1;  
 }  
 else{  
 left = mid + 1;  
 }  
 }  
 // всі числа відсортовані за зростанням між mid і right  
 else{   
 if(nums[mid] <= target && target <= nums[right]){  
 left = mid+1;  
 }  
 else{  
 right = mid-1;  
 }  
 }  
 }  
 return -1;   
 }  
};

Підсушування коду з прикладом

Вхід:

• nums = [4,5,6,7,0,1,2]
• target = 0

Ітерація 1:

• Початковий діапазон: left = 0, right = 6, mid = (0 + 6) / 2 = 3.
• nums[mid] = 7, nums[left] = 4, nums[right] = 2.
• Ліва частина відсортована (nums[mid] >= nums[left]).
• Цільове значення 0 не знаходиться в діапазоні [nums[left], nums[mid]] = [4,7].
• Звужуємо пошук праворуч: left = mid + 1 = 4

Ітерація 2:

• Оновлений діапазон: left = 4, right = 6, mid = (4 + 6) / 2 = 5.
• nums[mid] = 1, nums[left] = 0, nums[right] = 2.
• Ліва частина відсортована (nums[mid] >= nums[left]).
• Цільове значення 0 знаходиться в діапазоні [nums[left], nums[mid]] = [0,1].
• Звужуємо пошук ліворуч: right = mid - 1 = 4

Ітерація 3:

• Оновлений діапазон: left = 4, right = 4, mid = (4 + 4) / 2 = 4.
• nums[mid] = 0, що збігається з цільовим значенням.
• Повертаємо 4

Вихід:

• Індекс 4

Якщо вам сподобалося це пояснення концепцій, будь ласка, підписуйтесь, слідкуйте та ставте лайки

Перекладено з: Understanding Searching Algorithms in C++: Guide to Linear and Binary Search