ความแตกต่างระหว่างการค้นหาแบบไบนารีและการค้นหาแบบ Linear

การค้นหาแบบ Binary หรือ Linear Search

การค้นหาแบบ Linear หรือที่เรียกว่าการค้นหาตามลำดับคืออัลกอริทึมการค้นหาที่ง่ายที่สุด จะค้นหาค่าที่ระบุในรายการด้วยการตรวจสอบองค์ประกอบทั้งหมดในรายการ การค้นหาแบบไบนารีเป็นวิธีที่ใช้เพื่อค้นหาค่าที่ระบุในรายการที่เรียงลำดับ วิธีการค้นหาแบบไบนารีจะลดจำนวนขององค์ประกอบที่ตรวจสอบลง (ในแต่ละรอบ) ลดเวลาในการค้นหารายการที่กำหนดในรายการ

Linear Search คืออะไร?

การค้นหาแบบ Linear คือวิธีการค้นหาที่ง่ายที่สุดซึ่งจะตรวจสอบแต่ละองค์ประกอบในรายการตามลำดับจนกว่าจะพบองค์ประกอบที่ระบุ การป้อนข้อมูลลงในวิธีการค้นหาเชิงเส้นเป็นลำดับ (เช่นอาร์เรย์คอลเล็กชันหรือสตริง) และรายการที่ต้องค้นหา ผลลัพธ์เป็นจริงหากรายการที่ระบุอยู่ภายในลำดับที่ระบุหรือเท็จถ้าไม่ได้อยู่ในลำดับ เนื่องจากวิธีนี้จะตรวจสอบทุกรายการในรายการจนกว่าจะพบรายการที่ระบุไว้ในกรณีที่เลวร้ายที่สุดจะไปถึงองค์ประกอบทั้งหมดในรายการก่อนที่จะพบองค์ประกอบที่ต้องการ ความซับซ้อนของการค้นหาเชิงเส้นคือ o (n) ดังนั้นจึงถือว่าช้าเกินไปที่จะใช้เมื่อค้นหาองค์ประกอบในรายการขนาดใหญ่ แต่นี้ง่ายมากและง่ายต่อการใช้

การค้นหาแบบไบนารีคืออะไร?

การค้นหาแบบไบนารีเป็นวิธีที่ใช้ค้นหารายการที่ระบุในรายการที่เรียงลำดับ วิธีนี้เริ่มต้นด้วยการเปรียบเทียบส่วนประกอบที่สืบค้นไปยังองค์ประกอบที่อยู่ตรงกลางของรายการ ถ้าการเปรียบเทียบระบุว่าองค์ประกอบทั้งสองมีค่าเท่ากันวิธีหยุดและส่งกลับตำแหน่งขององค์ประกอบ หากองค์ประกอบที่ค้นหามีขนาดใหญ่กว่าองค์ประกอบตรงกลางจะเริ่มใช้เมธอดอีกครั้งโดยใช้เฉพาะครึ่งล่างของรายการที่เรียง หากองค์ประกอบที่ค้นหาน้อยกว่าองค์ประกอบตรงกลางจะเริ่มต้นใช้เมธอดอีกครั้งโดยใช้เพียงครึ่งบนของรายการที่เรียง หากองค์ประกอบที่สืบค้นไม่อยู่ในรายการเมธอดจะคืนค่าที่ไม่ซ้ำซึ่งระบุว่า ดังนั้นวิธีการค้นหาแบบไบนารีจึงลดจำนวนขององค์ประกอบลงครึ่งหนึ่ง (ในแต่ละการทำซ้ำ) ขึ้นอยู่กับผลการเปรียบเทียบ ดังนั้นการค้นหาไบนารีจะทำงานในเวลาลอการิทึมซึ่งส่งผลให้ประสิทธิภาพของกรณีโดยเฉลี่ย o (log n)

อะไรคือความแตกต่างระหว่างการค้นหาแบบไบนารีและการค้นหาแบบ Linear?

แม้ว่าทั้งการค้นหาเชิงเส้นและการค้นหาไบนารีกำลังค้นหาวิธีที่พวกเขามีความแตกต่างกัน ขณะที่การค้นหาแบบไบนารีดำเนินการกับรายการที่เรียงลำดับการค้นหาซับยังสามารถทำงานได้ในรายการที่ไม่ได้เรียงลำดับเช่นกัน การเรียงลำดับรายการโดยทั่วไปมีความซับซ้อนกรณีเฉลี่ยของ n log n การค้นหาแบบเชิงเส้นทำได้ง่ายและตรงไปตรงมากว่าการค้นหาแบบไบนารี แต่การค้นหาเชิงเส้นช้าเกินไปที่จะใช้กับรายการขนาดใหญ่เนื่องจากประสิทธิภาพในการทำงานของ O (n) โดยเฉลี่ยในทางกลับกันการค้นหาแบบไบนารีถือเป็นวิธีที่มีประสิทธิภาพมากขึ้นซึ่งสามารถนำมาใช้กับรายการขนาดใหญ่ได้ แต่การใช้การค้นหาแบบไบนารีอาจค่อนข้างยุ่งยากและการศึกษาได้แสดงให้เห็นว่ารหัสที่ถูกต้องสำหรับการค้นหาแบบไบนารีสามารถพบได้ในหนังสือเพียง 5 เล่มจาก 20 เล่ม