ორობითი ძიების (Binary Search) ალგორითმი PHP-ში: ახსნა, ნაბიჯები და მაგალითი

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

ნაბიჯები:

1. საძიებო დიაპაზონის ინიცირება: დაიწყეთ საძიებო დიაპაზონის არჩევით  მასივის პირველი პოზიციიდან left  ბოლო პოზიციამდე. right
2. იპოვეთ შუა წერტილი: გამოთვალეთ შუა წერტილი პოზიციების left და მარჯვენა პოზიციების საშუალოდ; ეს არის საძიებო დიაპაზონის შუა წერტილი.
3. მნიშვნელობების შედარება: შეადარეთ მნიშვნელობა შუა წერტილში სამიზნე მნიშვნელობასთან.
4. სახელურის შედარების შედეგი: თუ შუა წერტილის მნიშვნელობა ემთხვევა სამიზნე მნიშვნელობას, დააბრუნეთ ეს პოზიცია. თუ შუა წერტილში მნიშვნელობა სამიზნე მნიშვნელობაზე ნაკლებია, განაახლეთ მარცხენა პოზიცია შუაზე + 1 მარჯვენა ნახევრის მოსაძებნად. თუ შუა წერტილში მნიშვნელობა აღემატება სამიზნე მნიშვნელობას, განაახლეთ მარჯვენა პოზიცია შუაზე- 1 მარცხენა ნახევრის მოსაძებნად.
5. გაიმეორეთ: გაიმეორეთ ნაბიჯები 2-დან 4-მდე, სანამ არ მოიძებნება მნიშვნელობა ან არ იქნება მეტი ელემენტი შესამოწმებლად left > right.

Დადებითი და უარყოფითი მხარეები

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

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

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

• გამოიყენება მხოლოდ დახარისხებულ მასივებზე: ალგორითმი მუშაობს მხოლოდ დახარისხებულ მასივებზე.
• ნაბიჯების ცვლადი რაოდენობა: მნიშვნელობის მოსაძებნად საჭირო ნაბიჯების რაოდენობა დამოკიდებულია მის პოზიციაზე მასივში და მას შეუძლია მრავალი ნაბიჯის გადადგმა ბოლოების მახლობლად მდებარე მნიშვნელობებისთვის.

მაგალითი: ორობითი ძიება PHP-ში დახარისხებულ მასივში მნიშვნელობის 12-ის საპოვნელად

function binarySearch($arr, $target) {  
    $left = 0;  
    $right = count($arr)- 1;  
  
    while($left <= $right) {  
        $mid = floor(($left + $right) / 2);  
  
        if($arr[$mid] == $target) {  
            return $mid; // Return the position of the value  
        } elseif($arr[$mid] < $target) {  
            $left = $mid + 1;  
        } else {  
            $right = $mid- 1;  
        }  
    }  
  
    return -1; // Value not found  
}  
  
$array = [2, 5, 8, 12, 15, 20, 30];  
$targetValue = 12;  
  
$result = binarySearch($array, $targetValue);  
  
if($result != -1) {  
    echo "Value $targetValue found at position $result.";  
} else {  
    echo "Value $targetValue not found in the array.";  
}  

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

1. ჩვენ ვიწყებთ საწყისი ძიების დიაპაზონს  მასივის პირველი პოზიციიდან left = 0 ბოლო პოზიციამდე. right = 6
2. ჩვენ ვიანგარიშებთ შუა წერტილს(შუა) მარცხენა და მარჯვენა პოზიციების საშუალოდ; mid = 3. ღირებულება შუა რიცხვებში არის 12.
3. ჩვენ ვადარებთ მნიშვნელობას mid(12)-ს სამიზნე მნიშვნელობასთან(12) და ვპოულობთ შესატყვისს, ასე რომ ვაბრუნებთ მე-3 პოზიციას.
4. ალგორითმი მთავრდება და ჩვენ გამოვიყვანთ შედეგს "მნიშვნელობა 12 ნაპოვნი მე-3 პოზიციაზე."