Binary Search Python: คู่มือทีละขั้นตอน

Python binary search หาตำแหน่งของรายการในอาร์เรย์ที่จัดเรียงแล้ว มันแบ่งรายการครึ่งหนึ่ง หากค่าที่ระบุสูงกว่าตัวเลขกลาง การค้นหาจะเน้นด้านขวาของรายการ มิฉะนั้น การค้นหาจะมองหาตัวเลขด้านซ้ายของรายการ

คุณหาตำแหน่งของรายการในรายการอย่างไร? Binary searches ช่วยคุณในเรื่องนั้น ด้วยการใช้ binary searches คุณสามารถหาตำแหน่งขององค์ประกอบภายในอาร์เรย์ที่จัดเรียงแล้วได้อย่างง่ายดาย

คอมพิวเตอร์เก่งในการค้นหาผ่านรายการเพื่อหารายการเฉพาะ กฎที่คอมพิวเตอร์ใช้เพื่อหารายการในรายการเรียกว่าอัลกอริทึมการค้นหา (search algorithms) หนึ่งในอัลกอริทึม Python ที่นิยมที่สุดคือ binary search

ในคู่มือนี้ เราจะอภิปรายว่า binary searches คืออะไรและทำงานอย่างไร เราจะเดินทางผ่านตัวอย่างของ binary search ใน Python เพื่อให้คุณเรียนรู้วิธีเขียนมันลงในโปรแกรมของคุณ มาเริ่มกัน!

Python Binary Search คืออะไร? (What is a Python Binary Search?)

Python binary search เป็นอัลกอริทึมที่หาตำแหน่งขององค์ประกอบในอาร์เรย์ที่จัดเรียงแล้ว Binary searches แบ่งรายการซ้ำๆ เป็นสองครึ่ง จากนั้น การค้นหาเปรียบเทียบว่าค่าสูงกว่าหรือต่ำกว่าค่ากลางในรายการ

มีสองวิธีที่คุณสามารถดำเนินการ binary search ได้ ทั้งสองแนวทางตั้งค่า pointer (ตัวชี้) ซึ่งใช้ติดตามตำแหน่งสูงสุดและต่ำสุดในจุดเฉพาะในอาร์เรย์

แนวทางแรกที่คุณสามารถใช้คือ iterative method (วิธีวนซ้ำ) ในแนวทางนี้ ชุดของคำสั่งจะถูกทำซ้ำเพื่อกำหนดตำแหน่งขององค์ประกอบในอาร์เรย์ ใน Python เราใช้ลูป while สำหรับวัตถุประสงค์นี้

แนวทางอีกอันคือ recursive method (วิธีเรียกซ้ำ) นี่คือที่ที่คุณเขียนฟังก์ชันที่เรียกตัวเองซ้ำๆ จนกว่าจะพบองค์ประกอบในรายการ วิธีเรียกซ้ำใช้แนวทางแบ่งและพิชิต (divide and conquer) ที่เราอภิปรายก่อนหน้านี้และทำซ้ำกระบวนการค้นหาจนกว่าจะพบองค์ประกอบ

Binary Search Tree Python: ขั้นตอนทีละขั้น (Step-by-Step)

ด้วยการพูดคุยมากมายเกี่ยวกับการแบ่งและพิชิตและการเรียกซ้ำ อาจง่ายที่จะหลุดจากการทราบอย่างแน่นอนว่า binary search ทำงานอย่างไร เพื่อเหตุผลนั้น เราจะกระโดดเข้าไปในตัวอย่างของวิธีที่ binary search ทำงานโดยตรง พิจารณารายการต่อไปนี้:

เราจะค้นหาตัวเลข "22" ในรายการของเรา

เริ่มต้น เราจะตั้งค่าตัวชี้สองตัวในรายการของเรา ตัวชี้หนึ่งจะสะท้อนค่าสูงสุดในรายการ และอีกตัวชี้จะสะท้อนค่าต่ำสุด:

ขั้นตอนต่อไปของเราคือการหาองค์ประกอบกลางในอาร์เรย์ ซึ่งคือ 14 หากค่านี้เท่ากับค่าที่เรากำลังค้นหา ค่านี้ควรถูกคืนค่า

ในกรณีนี้ 14 ไม่เท่ากับ 22 ดังนั้น โปรแกรมของเราต้องทำการเปรียบเทียบ

เราจะเปรียบเทียบตัวเลขที่เรากำลังค้นหากับองค์ประกอบกลางขององค์ประกอบด้านขวาขององค์ประกอบกลางปัจจุบัน เราจะทำเช่นนี้ก็ต่อเมื่อตัวเลขที่เราค้นหาสูงกว่าตัวเลขกลาง มิฉะนั้น เราจะเปรียบเทียบองค์ประกอบกับองค์ประกอบกลางด้านซ้ายขององค์ประกอบกลางปัจจุบัน

ตัวเลข 22 สูงกว่า 14 โปรแกรมของเราเริ่มเปรียบเทียบ 22 กับองค์ประกอบกลางด้านขวาขององค์ประกอบกลางปัจจุบันของเรา (14) ในกรณีนี้ ตัวเลขนั้นคือ 22 นี่เท่ากับตัวเลขที่เรากำลังค้นหา

เราพบค่ากลางของเราแล้ว โปรแกรมของเราจะคืนค่าตำแหน่งดัชนีของตัวเลขนั้น ในกรณีนี้ ตำแหน่งดัชนีของ 22 คือ 3 (จำไว้ รายการมีดัชนีเริ่มจาก 0!)

วิธีนำ Binary Search ไปใช้ใน Python (How to Implement a Binary Search in Python)

มาล้างมือกับโค้ด Python บ้าง เราจะสำรวจการนำ binary search ไปใช้ใน Python โดยใช้ทั้งสองแนวทางที่เราอภิปรายก่อนหน้านี้: วิธีวนซ้ำ (iterative) และวิธีเรียกซ้ำ (recursive)

Iterative Binary Search ใน Python (วนซ้ำ)

เราจะเริ่มต้นด้วยวิธีวนซ้ำ นี่คือที่ที่เราจะวนซ้ำผ่านทุกรายการในรายการของเรา จากนั้น เราจะหาค่ากลางในรายการ เราจะทำเช่นนี้ต่อไปจนกว่าเราจะพบค่าที่เรากำลังมองหา

ฟังก์ชัน Binary Search (Binary Search Function)

มาเริ่มต้นด้วยการกำหนดฟังก์ชัน Python สำหรับ binary search ของเรา:

def findValue(numbers, number_to_find):
    low = 0
    high = len(numbers) - 1
    while low <= high:
        middle = low + (high - low) // 2
        if numbers[middle] == number_to_find:
            return middle
        elif numbers[middle] < number_to_find:
            low = middle + 1
        else:
            high = middle - 1
    return -1 

ฟังก์ชันของเรายอมรับสองพารามิเตอร์: รายการที่เราต้องการค้นหา และตัวเลขที่เราต้องการหาในรายการของเรา

เราจึงประกาศตัวแปร Python สองตัวที่จัดเก็บค่าเริ่มต้นสำหรับค่าต่ำสุดและสูงสุดในรายการ low ตั้งค่าเป็น 0 ซึ่งเป็นค่าดัชนีเริ่มต้นในรายการ high ตั้งค่าเป็นความยาวของรายการลบหนึ่ง (เพราะรายการมีดัชนีเริ่มจากศูนย์)

ขั้นตอนต่อไปของเราคือการประกาศลูป while ของ Python ลูปนี้รันในขณะที่องค์ประกอบต่ำสุดน้อยกว่าหรือเท่ากับตัวเลขสูงสุด นี่หมายความว่าลูปของเราจะรันก็ต่อเมื่อตัวเลขของเรายังไม่ถูกพบ

จากนั้น เราคำนวณตัวเลขกลาง เราทำได้โดยการลบค่าต่ำสุดจากค่าสูงสุด เราจึงคำนวณโมดุล로 (เศษ) ของตัวเลขนั้นเมื่อหารด้วย 2 จากนั้น เราบวกโมดุลโลกับค่าของตัวเลขต่ำสุด

หากตัวเลขกลางในรายการของเราเท่ากับตัวเลขที่เราต้องการหา เราคืนค่าตำแหน่งของตัวเลขนั้น

เราตั้ง "low" ใหม่ของเราให้เท่ากับหนึ่งมากกว่าตำแหน่งกลาง นี่เกิดขึ้นหากตัวเลขกลางน้อยกว่าตัวเลขที่เราต้องการหา นี่เลื่อนการค้นหาของเราลงไปด้านซ้ายของรายการของเรา เหมือนที่เราทำในตัวอย่างภาพก่อนหน้านี้

มิฉะนั้น เราตั้ง "high" ใหม่ของเราให้เท่ากับหนึ่งน้อยกว่าตำแหน่งกลาง นี่เลื่อนการค้นหาของเราไปด้านขวาของรายการของเรา

สิ่งนี้ทำซ้ำจนกว่า low จะเท่ากับหรือน้อยกว่า high หากค่าของเราไม่ถูกพบ เราคืนค่า -1 เราจะพูดถึงเหตุผลในหนึ่งนาที

รันการค้นหา (Execute the Search)

เพิ่มโค้ดต่อไปนี้ที่ด้านล่างของโปรแกรมของคุณ นอกเหนือจากฟังก์ชัน findValue:

numbers = [7, 9, 14, 22, 34]
number_to_find = 22
final = findValue(numbers, number_to_find)
if final == -1:
    print("This item was not found in the list.")
else:
    print("The number " + str(number_to_find) + " was found at index position " + str(final) + ".") 

เราเริ่มต้นด้วยการประกาศรายการรายการที่เราต้องการค้นหา จากนั้นเราได้ระบุตัวเลขที่เราต้องการหา ซึ่งคือ 22

ต่อไป เราเรียกฟังก์ชัน findValue() ของเราและส่งผ่านมันรายการ

นี่คือที่ที่ -1 มาจากก่อนหน้านี้ หากตัวเลขที่คืนค่าโดยฟังก์ชันของเราคือ -1 นั่นหมายความว่ารายการของเราไม่ถูกพบในรายการ โปรแกรมเมอร์มักใช้ -1 ในสถานการณ์เช่นนี้เพราะฟังก์ชันค้นหาของเราไม่สามารถคืนค่าตัวเลขลบได้

มิฉะนั้น โปรแกรมของเราพิมพ์ข้อความบอกเราตำแหน่งดัชนีของค่านั้น

โค้ดของเราคืนค่า:

The number 22 was found at index position 3.

ตอนนี้เรารู้ว่าตัวเลข 22 ปรากฏที่ตำแหน่งดัชนี 3

Recursive Binary Search ใน Python (เรียกซ้ำ)

เราสามารถใช้การเรียกซ้ำเพื่อดำเนินการ binary search ได้อีกด้วย นี่คือที่ที่เราจะกำหนดฟังก์ชันที่เรียกตัวเองต่อไปจนกว่าเงื่อนไข – การพบตัวเลขของเรา – จะเป็นจริง

กำหนดฟังก์ชันเรียกซ้ำ (Define a Recursive Function)

เหมือนในตัวอย่างล่าสุดของเรา เราจะเริ่มต้นด้วยการเขียนฟังก์ชันที่ดำเนินการ binary search ของเรา:

def findValue(numbers, number_to_find, low, high):
    if high >= low:
        middle = low + (high - low) // 2
        if numbers[middle] == number_to_find:
            return middle
        elif numbers[middle] < number_to_find:
            return findValue(numbers, number_to_find, middle + 1, high)
        else:
            return findValue(numbers, number_to_find, low, middle - 1)
    else:
        return -1 

โค้ดของเราค่อนข้างคล้ายกับตัวอย่างล่าสุดของเรา

เราเริ่มต้นด้วยการตรวจสอบว่าค่าสูงสุดมากกว่าหรือเท่ากับ low หรือไม่ หากเป็นเช่นนั้น โปรแกรมของเราจะคืนค่า -1 มิฉะนั้น มันจะเริ่มดำเนินการ binary search

เราคำนวณตัวเลขกลางโดยใช้แนวทางเดียวกับตัวอย่างล่าสุด ก่อนอื่น เราลบค่าต่ำสุดจากค่าสูงสุด จากนั้น เราคำนวณโมดุลโล (เศษ) ของค่านั้นเมื่อหารด้วย 2 สุดท้าย เราบวกตัวเลขต่ำสุด

เราจึงเขียนคำสั่ง if ซึ่งตัดสินใจว่าการค้นหา binary ของเราควรดำเนินต่อไปอย่างไร:

• หากตัวเลขกลางเท่ากับตัวที่เรากำลังมองหา ตำแหน่งของตัวเลขนั้นจะถูกคืนค่า
• หากตัวเลขกลางน้อยกว่าตัวที่เรากำลังมองหา ฟังก์ชัน findValue() ของเราจะถูกเรียกอีกครั้ง ครั้งนี้ ค่าของ low จะถูกตั้งค่าให้เท่ากับหนึ่งมากกว่าค่ากลางของเรา
• หากตัวเลขกลางมากกว่าตัวที่เรากำลังมองหา ฟังก์ชัน findValue() จะถูกเรียก ค่าของ "high" จะเท่ากับหนึ่งน้อยกว่าค่ากลาง

เขียนโปรแกรมหลัก (Write the Main Program)

สิ่งที่เหลือให้เราทำคือเขียนโปรแกรมหลักของเรา:

numbers = [7, 9, 14, 22, 34]
number_to_find = 22
final = findValue(numbers, number_to_find, 0, len(numbers) - 1)
if final == -1:
    print("This item was not found in the list.")
else:
    print("The number " + str(number_to_find) + " was found at index position " + str(final) + ".") 

โปรแกรมหลักของเราเหมือนกับตัวอย่างก่อนหน้านี้ ยกเว้นความแตกต่างหนึ่ง เราส่งผ่านพารามิเตอร์ใหม่สองตัวให้ฟังก์ชัน findValue() ของเรา: low และ high

เราต้องทำเช่นนี้เพราะอัลกอริทึมของเราเป็นแบบเรียกซ้ำ และเราไม่สามารถกำหนดค่าเหล่านั้นในฟังก์ชันของเราได้ หากเรากำหนดค่าในฟังก์ชันของเรา ค่าเหล่านั้นจะถูกรีเซ็ตทุกครั้งที่ฟังก์ชันของเรารัน ซึ่งจะทำให้อัลกอริทึมค้นหาของเราเสียหาย

โค้ดของเราคืนค่า:

The number 22 was found at index position 3.

เราได้รับผลลัพธ์เดียวกันจากก่อนหน้านี้ ในตัวอย่างนี้ เราใช้โปรแกรมแบบเรียกซ้ำแทนโปรแกรมแบบวนซ้ำเพื่อดำเนินการ binary search ของเรา

เมื่อไหร่ควรใช้ Python Binary Search? (When Should You Use a Python Binary Search?)

Binary search เป็นวิธีที่มีประสิทธิภาพในการค้นหาผ่านรายการตัวเลข การค้นหานี้มีประสิทธิภาพมากกว่าการค้นหาเชิงเส้น (linear search) เนื่องจากวิธี binary ตัดการค้นหาของคุณลงครึ่งหนึ่งทันทีที่คุณพบกลางของรายการที่จัดเรียงแล้ว

สำคัญที่ต้องบันทึกไว้ว่ารายการต้องจัดเรียงตามตัวเลขก่อนที่จะค้นหาโดยใช้ binary search ได้ ก่อนที่คุณจะดำเนินการ binary search ตรวจสอบให้แน่ใจว่าตัวเลขของคุณจัดเรียงในลำดับขึ้น (ascending order)

Binary Search ใน Python Complexity Breakdown (การแยกความซับซ้อน)

ความซับซ้อนของ binary search คืออะไร? นั่นเป็นคำถามที่ดี

อัลกอริทึม binary search มีความซับซ้อนกรณีดีที่สุด (best case complexity) ของ O(1) สิ่งนี้เกิดขึ้นเมื่อการเปรียบเทียบครั้งแรกเท่ากับรายการที่คุณกำลังค้นหา

ความซับซ้อนกรณีเฉลี่ยและกรณีแย่ที่สุด (average and worst case complexity) สำหรับ binary search คือ O(log n) นี่หมายความว่าระยะเวลาที่ใช้ในการดำเนินการค้นหาเพิ่มขึ้นแบบลอการิทึม ขึ้นอยู่กับว่ามีรายการกี่รายการที่ต้องค้นหาในรายการ

สรุป

Binary searches เป็นวิธีที่มีประสิทธิภาพในการหาตำแหน่งดัชนีของค่าในรายการ

ทุกครั้งที่ binary search ถูกรัน การค้นหาจะแบ่งรายการออกเป็นสองส่วน การค้นหาเน้นด้านของรายการที่ใกล้ที่สุดกับตัวเลขที่คุณกำลังค้นหา

สำหรับแต่ละครั้งที่การค้นหาถูกรัน จำนวนตัวเลขที่โปรแกรมต้องค้นหาจะลดลงครึ่งหนึ่ง

หากต้องการเรียนรู้เพิ่มเติมเกี่ยวกับ Python โปรดอ่านคู่มือ How to Learn Python ของเรา