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