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

ორობითი (ბინარული) ძებნის ალგორითმი — საძიებო ალგორითმი, რომელიც პოულობს გარკვეული მნიშვნელობის პოზიციას დახარისხებულ (სორტირებულ) მასივში. ის უარეს შემთხვევაში ლოგარითმულ დროში მუშაობს, აკეთებს $O(\log n)$ შედარებას, სადაც $n$ არის ელემენტების რაოდენობა მასივში, $O$ არის ასიმპტოტური აღნიშვნა O-დიდი და $\log$ არის ლოგარითმი ფუძით 2. დიდ მასივებში ორობითი ძებნა გაცილებით სწრაფია ვიდრე წრფივი ძებნა, თუმცა, აუცილებელია მასივი იყოს დახარისხებული, რათა შევძლოთ მოცემული ალგორითმის გამოყენება.

ალგორითმი

დავუშვათ, A მასივის ელემენტები დალაგებულია ზრდადობის მიხედვით. ალგორითმი ითვალისწინებს მასივის შუა ელემენტის მოძებნას, რომლის მნიშვნელობაც უნდა შედარდეს წინასწარ მოცემული ცვლადის მნიშვნელობას; თუ მათი მნიშვნელობები დაემთხვა, ეს ნიშნავს, რომ საჭირო ელემენტი მოიძებნა მასივში და ძიების პროცესი წყდება. წინააღმდეგ შემთხვევაში, თუ ცვლადის მნიშვნელობა აღმოჩნდება ნაკლები მასივის შუა ელემენტის მნიშვნელობაზე, ძიება წარმოებს მასივის პირველ ნახევარში, ხოლო თუ ცვლადის მნიშვნელობა გადააჭარბებს მასივის შუა ელემენტის მნიშვნელობას, ძიება ხორციელდება საწყისი მასივის მეორე ნახევარში. ამდენად, ძიების პირველივე ეტაპზე ადგილი აქვს მასივის განახევრებას, შემდეგ მიღებული ნახევრებიდან ერთ-ერთის იგნორირების გზით და მასივის მეორე ნახევრის შუაზე გაყოფით ძებნა წარმოებს საწყისი მასივის მეოთხედში და ა.შ. პროცესი გრძელდება მანამდე, სანამ მასივის ერთ-ერთი ნახევრის შუა ელემენტის მნიშვნელობა არ დაემთხვევა მოცემული ცვლადის მნიშვნელობას, ან სანამ საჭირო ელემენტი არ მოიძებნება.

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

მეთოდი 1:

int binarySearch(const vector<int>& vec,const int& x){
    int start=0,end=vec.size()-1,mid;
    while(start<=end){
        mid=start+(end-start)/2;
        if(vec[mid]==x)return mid;
        else if(vec[mid]>x)end=mid-1;
        else start=mid+1;
    }return -1;
}

მეთოდი 2:

int binarySearch(const vector<int>& vec,const int& x){
    int k=0,n=vec.size();
    for(int i=n/2; i>=1; i/=2)
        while(k+i<n&&vec[k+i]<=x)
            k+=i;

    return vec[k]==x?k:-1;
}

ლიტერატურა

• ნონა ოთხოზორია, ლელა გაჩეჩილაძე, პროგრამული უზრუნველყოფის დეველოპერი, გვ. 72, 2015 წ.
• Antti Laaksonen, Competitive Programmer's Handbook, p. 32.