ორობითი ძებნის ალგორითმი: განსხვავება გადახედვებს შორის

მასალა ვიკიპედიიდან — თავისუფალი ენციკლოპედია
[შემოწმებული ვერსია][შემოწმებული ვერსია]
შიგთავსი ამოიშალა შიგთავსი დაემატა
No edit summary
No edit summary
ხაზი 1: ხაზი 1:
'''ორობითი (ბინარული) ძებნის ალგორითმი''' — საძიებო ალგორითმი, რომელიც პოულობს გარკვეული მნიშვნელობის პოზიციას დახარისხებულ (სორტირებულ) მასივში. ის უარეს შემთხვევაში ლოგარითმულ დროში მუშაობს, აკეთებს <math>O(\log n)</math> შედარებას, სადაც <math>n</math> არის ელემენტების რაოდენობა მასივში, <math>O</math> არის [[ასიმპტოტური აღნიშვნა O-დიდი]] და <math>\log</math> არის [[ლოგარითმი]]. დიდ მასივებში ორობითი ძებნა გაცილებით სწრაფია ვიდრე წრფივი ძებნა, თუმცა, აუცილებელია მასივი იყოს დახარისხებული, რათა შევძლოთ ორობითი ძებნის ალგორითმის გამოყენება.
'''ორობითი (ბინარული) ძებნის ალგორითმი''' — საძიებო ალგორითმი, რომელიც პოულობს გარკვეული მნიშვნელობის პოზიციას დახარისხებულ (სორტირებულ) მასივში. ის უარეს შემთხვევაში ლოგარითმულ დროში მუშაობს, აკეთებს <math>O(\log n)</math> შედარებას, სადაც <math>n</math> არის ელემენტების რაოდენობა მასივში, <math>O</math> არის [[ასიმპტოტური აღნიშვნა O-დიდი]] და <math>\log</math> არის [[ლოგარითმი]] ფუძით 2. დიდ მასივებში ორობითი ძებნა გაცილებით სწრაფია ვიდრე წრფივი ძებნა, თუმცა, აუცილებელია მასივი იყოს დახარისხებული, რათა შევძლოთ მოცემული ალგორითმის გამოყენება.


==ალგორითმი==
==ალგორითმი==
ხაზი 21: ხაზი 21:
int start=0,end=vec.size()-1,mid;
int start=0,end=vec.size()-1,mid;
while(start<=end){
while(start<=end){
mid=(start+end)/2;
mid=start+(end-start)/2;
if(vec[mid]==x)return mid;
if(vec[mid]==x)return mid;
else if(vec[mid]>x)end=mid-1;
else if(vec[mid]>x)end=mid-1;

00:20, 10 იანვარი 2020-ის ვერსია

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

ალგორითმი

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

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

მეთოდი 1:

int binarySearch(vector<int>vec,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(vector<int>vec,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.