Binary Search

हर चरण में आधा हटाएँ

Sorted array पर, लक्ष्य की मध्य तत्व से तुलना करें। यदि लक्ष्य बड़ा है, तो पूरा left आधा (mid सहित) अप्रासंगिक — left को उससे आगे ले जाएँ। अन्यथा right आधा हटाएँ। हर चरण search स्थान आधा: O(log n)।

Iterative टेम्पलेट

अन्य भाषाओं में overflow से बचने को left <= right और mid = left + (right-left)//2 उपयोग करें।

def binary_search(arr, target):
    lo, hi = 0, len(arr) - 1
    while lo <= hi:
        mid = lo + (hi - lo) // 2
        if arr[mid] == target:
            return mid
        if arr[mid] < target:
            lo = mid + 1     # target in right half
        else:
            hi = mid - 1     # target in left half
    return -1

Output:

binary_search([10,20,30,40,50,60,70,80], 60) -> 5

Dry run: 60 खोजें

[10 20 30 40 50 60 70 80]

• चरण 1: lo=0 hi=7 mid=3 → arr[3]=40 < 60 → lo=4
• चरण 2: lo=4 hi=7 mid=5 → arr[5]=60 → इंडेक्स 5 पर मिला

त्वरित जाँच: Binary search के लिए डेटा होना चाहिए...

• Sorted (या predicate पर monotonic)
• Hash map में संग्रहीत
• अभाज्य लंबाई का