What is Binary Search in DSA? | Complete Guide with PHP Example

If tutorials available on this website are helpful for you, please whitelist this website in your ad blocker😭 or Donate to help us ❤️ pay for the web hosting to keep the website running.

Binary Search by Marten Newhall on Unsplash

Binary Search एक बहुत ही efficient searching algorithm है जो sorted array या sorted list में data search करने के लिए use होता है। ये search करने कि speed को optimize करता है।

DSA (Data Structures and Algorithms) में Binary Search काफी important concept है, especially जब आपको large datasets के साथ काम करना हो।

आज के blog में, हम Binary Search को DSA course के perspective से समझेंगे और PHP code example के through इस concept को clear करेंगे।

●●●

Binary Search कि Basic Understanding

Binary Search का काम एक sorted array में दिया गया target element को efficiently search करना होता है। ये algorithm divide and conquer approach पर काम करता है, जिसमे array को recursively divide किया जाता है जब तक element मिल नहीं जाता।

Key Points:

• Sorted Array : Binary Search सिर्फ sorted array या list पर काम करता है, अगर data unsorted है, तो पहले sorting करना जरूरी है।

• Divide and Conquer : ये approach array को दो parts में divide करता है और हर part को independently search करता है। 

• Time Complexity : Binary Search का time complexity O(log n) होता है, जो कि linear search (O(n)) से काफी efficient है।
  

Binary Search Working

Binary Search algorithm को समझने के लिए, चलिए एक example लेते हैं। मान लीजिये हमारे पास एक sorted array है :

[1, 3, 5, 7, 9, 11, 13, 15, 17, 19]

और हमें 7 को search करना है, Binary Search का process कुछ इस तरह होगा -

1. Start : Array के पहले और आखिरी index को define करते हैं।

Left = 0

Right = 9 (last index)

2. Middle Element : अब array का middle element calculate करते हैं. Middle का index formula है :

Middle Index = (Left+Right)/2​

इस example में, middle element index 4 होगा (array[4] = 9).

3. Comparison : अब middle element (9) को target element (7) से compare करते हैं।

• अगर middle element target से बड़ा हो, तो search left half में continue होगा।

• अगर middle element target से छोटा हो, तो search right half में continue होगा।
  

4. Update Boundaries : Left और Right boundaries को update करते हैं और process को continue करते हैं जब तक target element मिल न जाये।

5. End Condition : अगर Left index ज़्यादा हो जाये Right index से, इसका मतलब target element नहीं मिला।

●●●

Binary Search Example

चलिए अब हम Binary Search को PHP में implement करते हैं।

Copy
<?php
// Binary Search function
function binarySearch($arr, $target) {
    $left = 0;
    $right = count($arr) - 1;
    
    while ($left <= $right) {
        // Find the middle element
        $mid = floor(($left + $right) / 2);
        
        // If the target element is found at the middle
        if ($arr[$mid] == $target) {
            return "Element found at index " . $mid;
        }
        
        // If the target element is greater than the middle element
        if ($arr[$mid] < $target) {
            $left = $mid + 1;
        } 
        // If the target element is smaller than the middle element
        else {
            $right = $mid - 1;
        }
    }
    
    return "Element not found";
}

// Example array (sorted)
$array = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19];

// Target element to search
$target = 7;

// Call the binary search function
echo binarySearch($array, $target);

Binary Search की Complexity

• Time Complexity : Binary Search का time complexity O(log n) होता है, जिसमे n array के elements कि total number होती है। ये log base 2 में होता है, क्योंकि array हर step पर half हो जाता है।

• Space Complexity : Space complexity O(1) होती है, क्योंकि हम array को in-place process करते हैं और extra space कि need नहीं होती।
  

●●●

Binary Search के Use Cases

Binary Search को बहुत से real-world problems में use किया जाता है. कुछ common use cases हैं -

• Searching in a Sorted Array : जैसे कि हमने example में देखा।

• Binary Search Trees : BSTs में Binary Search का use होता है। 

• Finding Closest Value : अगर exact match नहीं मिलता, तो nearest element find करना। 

Conclusion

Binary Search एक powerful algorithm है जो searching को काफी efficient बना देता है, especially जब data sorted हो। DSA के concepts में ये algorithm काफी useful है, और हर programmer को इसको अच्छे से समझना चाहिए।

●●●