पायथन प्रोग्राम: बाइनरी सर्च एल्गोरिदम

इस लेख में, हम दी गई समस्या के समाधान और दृष्टिकोण के बारे में जानेंगे।

समस्या कथन - हमें एक सॉर्ट की गई सूची दी जाएगी और हमें बाइनरी सर्च की मदद से एक तत्व ढूंढना होगा।

एल्गोरिदम

• x की तुलना मध्य तत्व से करें।

• यदि x मध्य तत्व से मेल खाता है, तो हम मध्य इंडेक्स वापस करते हैं।

• अन्यथा यदि x मध्य तत्व से बड़ा है, तो x केवल मध्य तत्व के बाद दाएं आधे सबएरे में हो सकता है। इसलिए हम दाएं आधे के लिए पुनरावृत्ति करते हैं।

• अन्यथा (x छोटा है) बाएं आधे के लिए पुनरावृत्ति करें

पुनरावर्ती एल्गोरिदम

उदाहरण

def binarySearchAppr(arr, start, end, x):
    # शर्त जांचें
    if end >= start:
        mid = start + (end - start)//2
        # यदि तत्व मध्य में मौजूद है
        if arr[mid] == x:
            return mid
        # यदि तत्व मध्य से छोटा है
        elif arr[mid] > x:
            return binarySearchAppr(arr, start, mid-1, x)
        # अन्यथा तत्व मध्य से बड़ा है
        else:
            return binarySearchAppr(arr, mid+1, end, x)
    else:
        # तत्व सरणी में नहीं मिला
        return -1

arr = sorted(['t','u','t','o','r','i','a','l'])
x = 'r'
result = binarySearchAppr(arr, 0, len(arr)-1, x)
if result != -1:
    print("Element is present at index " + str(result))
else:
    print("Element is not present in array")

पुनरावृत्त एल्गोरिदम

उदाहरण

def binarySearchAppr(arr, start, end, x):
    # शर्त जांचें
    if end >= start:
        mid = start + (end - start)//2
        # यदि तत्व मध्य में मौजूद है
        if arr[mid] == x:
            return mid
        # यदि तत्व मध्य से छोटा है
        elif arr[mid] > x:
            return binarySearchAppr(arr, start, mid-1, x)
        # अन्यथा तत्व मध्य से बड़ा है
        else:
            return binarySearchAppr(arr, mid+1, end, x)
    else:
        # तत्व सरणी में नहीं मिला
        return -1

arr = sorted(['t','u','t','o','r','i','a','l'])
x = 'r'
result = binarySearchAppr(arr, 0, len(arr)-1, x)
if result != -1:
    print("Element is present at index " + str(result))
else:
    print("Element is not present in array")

आउटपुट

Element is present at index 4

निष्कर्ष

इस लेख में, हमने बाइनरी सर्च लागू करने के दृष्टिकोण के बारे में सीखा।