ბინარული ძიების (Binary Search) ალგორითმი in Java

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

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

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

ორობითი ძიების ალგორითმის უპირატესობები და უარყოფითი მხარეები

უპირატესობები:

• მაღალი ეფექტურობა: ეს ალგორითმი აღმოფხვრის ელემენტების ნახევარს თითოეულ ნაბიჯში, ოპტიმიზაციას უწევს დიდი მასივების ძიებას.
• დაბალი დროის სირთულე: ამ ალგორითმის დროითი სირთულე არის O(log n), რაც მას ეფექტურს ხდის მონაცემთა დიდი ნაკრებისთვის.

ნაკლოვანებები:

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

მაგალითი და ახსნა

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

public class BinarySearchExample {  
    public static int binarySearch(int[] array, int target) {  
        int left = 0;  
        int right = array.length- 1;  
  
        while(left <= right) {  
            int mid = left +(right- left) / 2;  
  
            if(array[mid] == target) {  
                return mid; // Return position if found  
            } else if(array[mid] < target) {  
                left = mid + 1;  
            } else {  
                right = mid- 1;  
            }  
        }  
        return -1; // Return -1 if not found  
    }  
  
    public static void main(String[] args) {  
        int[] numbers = { 1, 3, 5, 7, 9, 11, 13, 15 };  
        int target = 9;  
  
        int position = binarySearch(numbers, target);  
  
        if(position != -1) {  
            System.out.println("Element " + target + " found at position " + position);  
        } else {  
            System.out.println("Element " + target + " not found in the array");  
        }  
    }  
}  

ამ მაგალითში, ჩვენ ვიყენებთ ორობითი ძიების ალგორითმს, რათა ვიპოვოთ ნომერი 9 დალაგებული მთელი რიცხვების მასივში. ალგორითმი იმეორებს მასივის მეშვეობით და ადარებს საძიებო მნიშვნელობას საშუალო მნიშვნელობასთან. ამ შემთხვევაში, რიცხვი 9 გვხვდება მასივში მე-4 პოზიციაზე(0-ზე დაფუძნებული ინდექსი).

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