โปรแกรม Python สำหรับการค้นหาแบบทวิภาค (Binary Search)

ในบทความนี้ เราจะเรียนรู้เกี่ยวกับวิธีแก้ปัญหาและแนวทางการแก้ปัญหาที่กำหนด

ข้อความของปัญหา − เราจะได้รับรายการที่เรียงลำดับแล้ว และเราต้องค้นหาองค์ประกอบด้วยการค้นหาแบบทวิภาค

อัลกอริทึม

• เปรียบเทียบ x กับองค์ประกอบกลาง

• ถ้า x ตรงกับองค์ประกอบกลาง ให้คืนค่าดัชนีกลาง

• ถ้า x มากกว่าองค์ประกอบกลาง x จะอยู่ได้แค่ครึ่งขวาของซับอาร์เรย์หลังองค์ประกอบกลาง ดังนั้นเราจึงทำซ้ำสำหรับครึ่งขวา

• ในกรณีอื่น (x น้อยกว่า) ทำซ้ำสำหรับครึ่งซ้าย

อัลกอริทึมแบบเรียกซ้ำ (Recursive)

ตัวอย่าง

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")

อัลกอริทึมแบบทำซ้ำ (Iterative)

ตัวอย่าง

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

สรุป

ในบทความนี้ เราได้เรียนรู้แนวทางในการนำ Binary Search ไปใช้งาน