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

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

const unsgined int N = 100 ; //розмір масиву даних 
char str[N] ; //наш масив даних (в даному випадку масив символів)

//заповнення масиву...

unsigned int i = 0 ; //ітератор для перебору
char c = 'a' ; //еталон пошуку 

while ( (i < N) && (str[i] != с) ) //цикл лінійного пошуку з інваріантою
{ i++ ; } //інкремент ітератора

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

const unsgined int N = 100 ; //розмір масиву даних 
char str[N] ; //наш масив даних (в даному випадку масив символів)

//заповнення масиву...

char c = 'a' ; //еталон пошуку

for (unsigned int i=0; i<N; ++i)
{
	if (str[i]==c)
	{ break; }
}

Або ж наш цикл можна записати наступним чином:

//...

for (unsigned int i=0; (i<N) && (str[i]!=c); ++i)
{}

А якщо нам необхідно знайти не один, а усі повторення елементу в масиві? Тобто елемент у масиві може повторятися не один раз. Наприклад, в слові "програмування", букви 'р', 'н' і 'а' зустрічаються по два рази. В такому разі ми можемо інжектувати в наш цикл код обробки знайденого елементу:

const unsgined int N = 100 ; //розмір масиву даних 
char str[N] ; //наш масив даних (в даному випадку масив символів)

//заповнення масиву...

char c = 'a' ; //еталон пошуку, наприклад буква 'а'

for (unsigned int i=0; i<N; ++i)
{
	if (str[i]==c)
	{
		//код обробки знайденого елементу
	}
}

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

void handle (unsigned int pos) //оголошена функція обробки входження з параметром позиції
{
	//код обробки
}

void search_algorithm (char* str, //масив даних у якому відбуватиметься пошук 
							  char c, //шуканий елемент масиву
							  void (*handler)(unsigned int) //функція обробки входження
							  )
{
    unsigned int N = strlen(str) ; //дізнаємося довжину масиву
    
    for (unsigned int i=0; i<N; ++i) //цикл пошуку
    {
	    if (str[i]==c) //перевірка еталону
	    {
		    handler(i) ; //якщо справджується умова - виконати обробку
	    }
    }
}

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

#include <iostream> //для виводу на екран
#include <string.h> //функція strlen
using namespace std; //використовуємо простір імен std

void handle (unsigned int pos) //оголошена функція обробки входження з параметром позиції
{
	std::cout << "знайдено за позицією: " << pos << endl ;
}

void search_algorithm (char* str, //масив даних у якому відбуватиметься пошук 
							  char c, //шуканий елемент масиву
							  void (*handler)(unsigned int) //функція обробки входження
							  )
{
    unsigned int N = strlen(str) ; //дізнаємося довжину масиву
    
    for (unsigned int i=0; i<N; ++i) //цикл пошуку
    {
	    if (str[i]==c) //перевірка еталону
	    {
		    handler(i) ; //якщо справджується умова - виконати обробку
	    }
    }
}

const char* message = "Beatifule world" ; //створений і заповнений масив

int main (int argc, char** argv) //головна функція програми
{
    char* str = (char*) message ;  
    char c = 'd' ; //еталон, себто шуканий елемент в масиві
    
    search_algorithm (str, c, &handle) ; //передаємо управління функції пошуку

    return 0 ; //вихід з програми
}

Після виконання її на комп'ютері ми отримаємо наступне:

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

#include  //вивід на екран
#include  //функція strlen
using namespace std; //використовуємо простір імен з iostream

unsigned int* search_algorithm (char* str, char c) //функція пошуку
{
    if (str==NULL) //перевірямо валідність вказівника
    { return NULL ; } //повертаємо вказівник NULL - ознака помилки
    
    unsigned int N = strlen(str) ; //розмір масиву даних
    
    /* Масив індексів входжень у масиві даних.
       Для безпки розглядається найгірша ситуація з точки зору використання
       пам'яті: у масиві усі елементи являються ідентичними еталону пошуку.
    */
    unsigned int *indexes = new unsigned int [N] ;
    
    //записуємо у пам'ять масиву нулі
    memset (indexes, 0, sizeof(unsigned int)) ; 
    
    unsigned int ind_pos = 0 ; /* ітератор масиву індексів */
    
    for (unsigned int i=0; i

Результат виконання програми:




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


#include  //вивід на екран
#include  //тип string
using namespace std; //використовуємо стандартний простір імен

//проста функція лінійного пошуку повертає найперший індекс входження
//якщо виникла помилка, або елемент не знайдено - повертає 
//значення менше від нуля
int search_algorithm (string str, //наші дані 
                      int pos, //позиція, з якої починати пошук
                      char c //еталон пошуку
                      ) 
{
    if (str.size()<1) //перевіряємо заповненість масиву
    { return (-1) ; } //повертаємо значення (-1) - ознака помилки
    
    unsigned int N = str.size() ; //розмір масиву даних
    
    for (int i=pos; i= 0) //виконуємо пошук
        {
            //виводимо повідомлення
            cout << "елемент '" << c << "' знайдено у позиції " << pos << endl ;
        }
    }
    while ( (pos>=0) && (pos


Результат виконання програми:


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

У бібліотеці STL існує реалізований алгоритм пошуку одного елемента в послідовності даних, у вигляді шаблонної функції. Вона знаходиться в заголовковому файлі algorithm і називається std::find.