წრფივი ძებნის ალგორითმი

წრფივი ძებნა — საძიებო ალგორითმი. მისი არსი შემდეგში მდგომარეობს: წინასწარ მოიცემა განსაზღვრული მნიშვნელობის მქონე ცვლადი და ის თანმიმდევრობით შედარდება მასივის ყველა ელემენტის მნიშვნელობას. თუ მასივის რომელიმე ელემენტის მნიშვნელობა დაემთხვევა მოცემული ცვლადის მნიშვნელობას, პროგრამა გამოიტანს შესაბამისი ელემენტის ინდექსს; წინააღმდეგ შემთხვევაში პროგრამა ამონახსნს ვერ გამოიტანს, ვინაიდან საჭირო მნიშვნელობის ელემენტი მასივში არ არსებობს. ამგვარად, ძებნის პროცესი აღნიშნული მეთოდის გათვალისწინებით გრძელდება მანამდე, სანამ არ შემოწმდება მასივის ყველა ელემენტი და არ მოიძებნება მათ შორის ისეთი, რომლის მნიშვნელობაც ტოლი იქნება მოცემული ცვლადის მნიშვნელობის (ცხადია, თუ ასეთი ელემენტი მასივში საერთოდ არსებობს).

ალგორითმი უარეს შემთხვევაში მუშაობს $O(n)$-დროში, უკეთეს შემთხვევაში კი $O(1)$-დროში.

აღნიშნული ალგორითმი მარტივია დაპროგრამების თვალსაზრისით, მაგრამ დიდი ზომის მასივების შემთხვევაში ხასიათდება არაეფექტურობით.

იმპლემენტაცია C++-ზე

#include <iostream>
using namespace::std;
int main(){
    //განვსაზღვროთ მასივის ზომა
    const int n=5;
    //შევქმნათ რაღაც მასივი
    int mas[n]={-123,5,1,-6,0};
    //შევქმნათ ცვლადი და მასში ჩავწეროთ იმ ელემენტის მნიშვნელობა, რომლის ინდექსსაც ვეძებთ მასივში
    int m;
    cout<<"shemoitanet mnishvneloba"<<endl;
    cin>>m;
    /*for-ციკლით გადავარჩიოთ ელემენტები, და თუ დაემთხვევა, გამოვიტანოთ ციკლის ცვლადი i
     და დავასრულოთ პროგრამა*/
    for(int i=0; i<n; i++){
        if(mas[i]==m){
            cout<<i;
            return 0;
        }
    }
    // თუ ვერ იპოვა გამოვიტანოთ შემდეგი:
    cout<<"elementi masivshi ar moidzebneba";
}

ლიტერატურა

• პროგრამული უზრუნველყოფის დეველოპერი. ნონა ოთხოზორია, ლელა გაჩეჩილაძე. 2015წ. (70გვ.).