ბინარული ძიება - binary search

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

წრფივი ძიება (linear search)

წარმოვიდგინოთ, რომ გვაქვს მასივი, რომელიც სორტირებულია ზრდის მიხედვით [1, 3, 5, 7, 9, 11, 13, 15], თუ ჩვენ შევეცდებით მაგალითად 13 რიცხვის ძიებას ე.წ. წრფივი ძიებით, (linear search) მოგვიწევს არსებულ მასივში შევამოწმოთ დასაწყისიდან 13-ის ჩათვლით ყველა ელემენტი, იმისთვის რომ მივაგნოთ არსებულ რიცხვს.

ამისთვის ჩვენს პროგრამას დასჭირდება 7 იტერაცია.

მაგალითი:

function linearSearch(arr, target) {
    let iterations = 0; // იტერაციის მთვლელი

    for (let i = 0; i < arr.length; i++) {
        iterations++; // ვზრდით იტერაციას 1-ით
        if (arr[i] === target) {
            console.log(`ვიპოვეთ ${target} მე-${i} ინდექსზე ${iterations} იტერაციაში.`);
            return arr[i];
        }
    }

    console.log(`${target} ვერ მოიძებნა ${iterations} იტერაციაში.`);
    return -1;
}

const numbers = [1, 3, 5, 7, 9, 11, 13, 15];

linearSearch(numbers, 13);

დაიბეჭდება:

ვიპოვეთ 13 მე-6 ინდექსზე 7 იტერაციაში.

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

ბინარული ძებნა (binary search)

ბინარული ძებნა მარტივად რომ ავხსნათ წარმოადგენს ალგორითმს, რომლის დროსაც არსებულ მასივს ვყოფთ შუაზე, მანამ სანამ საძიებო რიცხვს არ ვიპოვით.

როგორ მუშაობს ბინარული ძებნა?

1. ვპოულობთ მასივის შუა ელემენტს.
2. თუ ეს ელემენტი ემთხვევა საძიებო ელემენტს ვაბრუნებთ ამ ელემენტს და ვწყვეტთ პროგრამას.
3. თუ საძიებო ელემენტი ნაკლებია შუა ელემენტზე ძებნას ვაგრძელებთ მარცხენა ნაწილიში.
4. თუ საძიებო ელემენტი მეტია შუა ელემენტზე ძებნას ვაგრძელებთ მარჯვენა ნაწილში.
5. ვიმეორებთ 1-4 პუნქტებს მანამ სანამ არ მივაგნებთ ელემენტს ძიების დიაპაზონი არ იქნება ცარიელი.

მაგალითი:

function binarySearch(arr, target) {
    let left = 0;
    let right = arr.length - 1;
    let iterations = 0; // იტერაციის მთვლელი

    while (left <= right) {
        iterations++; // ვზრდით იტერაციას 1-ით
        let mid = Math.floor((left + right) / 2);

        if (arr[mid] === target) {
            console.log(`ვიპოვეთ ${target} მე-${mid} ინდექსზე ${iterations} იტერაციაში.`);
            return mid; // ელემენტი მოიძებნა
        }

        if (arr[mid] < target) {
            left = mid + 1; // ძიება მარჯვენა ნაწილში
        } else {
            right = mid - 1; // ძიება მარცხენა ნაწილში
        }
    }

    console.log(`${target} არ მოიძებნა ${iterations} იტერაციაში.`);
    return -1; // ელემენტი არ მოიძებნა
}

const numbers = [1, 3, 5, 7, 9, 11, 13, 15];

binarySearch(numbers, 13);

დაიბეჭდება:

 ვიპოვეთ 13 მე-6 ინდექსზე 3 იტერაციაში.

იტერაციების გარჩევა.

• პირველი იტერაცია.
  • left = 0, right = 7 → mid = Math.floor((0+7)/2) = 3
  • arr[3] = 7 (ნაკლებია 13-ზე) → ვაგრძელებთ ძებნას მარჯვენა ნაწილში (left = 4)

• მეორე იტერაცია.
  • left = 4, right = 7 → mid = Math.floor((4+7)/2) = 5
  • arr[5] = 11 (ნაკლებია 13-ზე) → ვაგრძელებთ ძებნას მარჯვენა ნაწილში (left = 6)

• მესამე იტერაცია.
  • left = 6, right = 7 → mid = Math.floor((6+7)/2) = 6
  • arr[6] = 13 (ელემენტი ვიპოვეთ) → ვაბრუნებთ 6

როგორც მაგალითებიდან დავინახეთ წრფივი ძიების დროს კოდს დასჭირდა 7 იტერაცია, ხოლო ბინარული ძიების დროს 3.

პ.ს.
აუცილებელია გვახსოვდეს, რომ ბინარული ძიება მუშაობს მხოლოდ სორტირებულ მასივებთან