อัลกอริทึมการค้นหาแบบไบนารี: ฟังก์ชัน ประโยชน์ เวลา & ความซับซ้อนของพื้นที่

บทนำ

ในระบบการคำนวณใดๆ การค้นหาเป็นหนึ่งในฟังก์ชันที่สำคัญที่สุดในการพัฒนา เทคนิคการค้นหาใช้ในการดึงไฟล์ การทำดัชนี และแอปพลิเคชันอื่นๆ อีกมากมาย มีเทคนิคการค้นหามากมาย หนึ่งในนั้นคือเทคนิคการค้นหาแบบไบนารี

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

ไม่จำเป็นต้องมีประสบการณ์การเข้ารหัส การสนับสนุนด้านอาชีพ 360° PG Diploma in Machine Learning & AI จาก IIIT-B และ upGrad

การทำงานของอัลกอริทึมการค้นหาแบบไบนารี

สิ่งแรกที่ควรทราบคือ อัลกอริธึมการค้นหาแบบไบนารี จะทำงานกับรายการที่เรียงลำดับเสมอ ดังนั้นขั้นตอนตรรกะแรกคือการเรียงลำดับรายการที่มีให้ หลังจากจัดเรียงแล้ว ค่ามัธยฐานของรายการจะถูกตรวจสอบด้วยค่าที่ต้องการ

• หากค่าที่ต้องการเท่ากับค่าดัชนีกลาง ดัชนีจะถูกส่งคืนเป็นคำตอบ

• หากค่าเป้าหมายต่ำกว่าข้อตกลงของดัชนีกลางของรายการ ด้านขวาของรายการจะถูกละเว้น

• หากค่าที่ต้องการมากกว่าค่าดัชนีกลาง ค่าครึ่งทางซ้ายจะถูกยกเลิก

• กระบวนการจะถูกทำซ้ำในรายการ shorted จนกว่าจะพบค่าเป้าหมาย

ตัวอย่าง #1

ให้เราดูอัลกอริธึมพร้อมตัวอย่าง สมมติว่ามีรายการที่มีหมายเลขต่อไปนี้:

1, 15, 23, 7, 6, 14, 8, 3, 27

ให้เราหาค่าที่ต้องการเป็น 27 จำนวนองค์ประกอบทั้งหมดในรายการคือ 9

ขั้นตอนแรกคือการเรียงลำดับรายการ หลังจากจัดเรียงแล้ว รายการจะมีลักษณะดังนี้:

1, 3, 6, 7, 8, 14, 15, 23, 27

เนื่องจากจำนวนองค์ประกอบในรายการมีเก้ารายการ ดัชนีกลางจะอยู่ที่ห้ารายการ ค่าที่ดัชนีห้าคือ 8 ค่าที่ต้องการคือ 27 เทียบกับค่า 8 ก่อนอื่น ให้ตรวจสอบว่าค่าเท่ากับ 8 หรือไม่ ถ้าใช่ ให้ส่งคืนดัชนีและออก

เนื่องจาก 27 มากกว่า 8 เราจะเพิกเฉยต่อส่วนด้านซ้ายและสำรวจเฉพาะด้านขวาของรายการเท่านั้น รายการใหม่ที่จะสำรวจคือ:

14, 15, 23, 27 ปี

หมายเหตุ: ในทางปฏิบัติ รายการจะไม่ถูกตัดทอน เฉพาะการสังเกตเท่านั้นที่แคบลง ดังนั้น "รายการใหม่" ไม่ควรสับสนกับการสร้างรายการใหม่หรือย่อรายการเดิม แม้ว่าจะสามารถนำไปใช้กับรายการใหม่ได้ แต่ก็มีปัญหาสองประการ ขั้นแรกจะมีหน่วยความจำอยู่เหนือศีรษะ รายการใหม่แต่ละรายการจะเพิ่มความซับซ้อนของพื้นที่ และอย่างที่สอง ต้องติดตามดัชนีดั้งเดิมในการวนซ้ำแต่ละครั้ง

ดัชนีกลางใหม่สามารถใช้เป็นองค์ประกอบที่สองหรือสามได้ ขึ้นอยู่กับการใช้งาน ในที่นี้ เราจะพิจารณาองค์ประกอบที่สามเป็นศูนย์กลาง ค่า 23 เปรียบเทียบกับค่า 27 เนื่องจากค่ามากกว่าค่าส่วนกลาง เราจะทิ้งค่าครึ่งทางซ้าย

รายการที่จะข้ามไปคือ:

27

เนื่องจากรายการมีองค์ประกอบเพียงองค์ประกอบเดียว จึงถือเป็นองค์ประกอบหลัก ดังนั้นเราจึงเปรียบเทียบค่าที่ต้องการกับ 27 เมื่อตรงกัน เราจะคืนค่าดัชนี 27 ในรายการเดิม

ตัวอย่าง #2

ในรายการเดียวกัน ให้เราสมมติค่าที่ต้องการเป็น 2

อันดับแรก ค่ากลางที่แปดจะถูกเปรียบเทียบกับ 2 เนื่องจากค่าที่ต้องการน้อยกว่าค่ากลาง เราจำกัดโฟกัสให้แคบลงทางด้านซ้ายของรายการ

การข้ามผ่านใหม่จะประกอบด้วย:

1, 3, 6, 7 ปี

ให้เรานำองค์ประกอบศูนย์กลางเป็นองค์ประกอบที่สอง ค่าที่ต้องการ 2 เปรียบเทียบกับ 3 เนื่องจากค่ายังน้อยกว่า เราจึงจำกัดโฟกัสให้แคบลงทางด้านซ้ายของรายการอีกครั้ง

การข้ามผ่านใหม่จะประกอบด้วย:

1

เนื่องจากรายการสำรวจมีองค์ประกอบเพียงองค์ประกอบเดียว ค่าจะถูกเปรียบเทียบกับองค์ประกอบที่เหลือโดยตรง เราเห็นว่าค่าไม่ตรงกัน ดังนั้นเราจึงแยกส่วนออกจากลูปด้วยข้อความแสดงข้อผิดพลาด: v alue not found

การรับรองขั้นสูงของ Data Science, พันธมิตรจ้างงานมากกว่า 250 ราย, การเรียนรู้มากกว่า 300 ชั่วโมง, 0% EMI

ความซับซ้อนของเวลาและอวกาศ

ความซับซ้อนของเวลาของ อัลกอริทึมการค้นหาแบบไบนารี คือ O(log n) ความซับซ้อนของเวลาในกรณีที่ดีที่สุดคือ O(1) เมื่อดัชนีกลางตรงกับค่าที่ต้องการโดยตรง กรณีที่เลวร้ายที่สุดอาจเป็นค่าที่ปลายสุดของรายการหรือค่าที่ไม่อยู่ในรายการ

ความซับซ้อนของพื้นที่ของ อัลกอริธึมการค้นหาแบบไบนารี ขึ้นอยู่กับการใช้งานอัลกอริธึม มีสองวิธีในการดำเนินการ:

1. วิธีการวนซ้ำ
2. วิธีการแบบเรียกซ้ำ

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

ในวิธีการวนซ้ำ ความซับซ้อนของช่องว่างจะเป็น O(1) ขณะที่อยู่ในวิธีการเรียกซ้ำ ความซับซ้อนของพื้นที่จะเป็น O(log n)

ประโยชน์

• อัลกอริธึมการค้นหา แบบ ไบนารีเป็นอัลกอริธึมการค้นหา ที่ค่อนข้างง่ายในการใช้งาน

• เป็นการปรับปรุงที่สำคัญเหนือการค้นหาเชิงเส้นและดำเนินการเกือบเหมือนกันเมื่อเปรียบเทียบกับอัลกอริธึมการค้นหาที่ยากกว่าบางตัว

• อัลกอริธึม การ ค้นหาแบบไบนารี แบ่งรายการลงครึ่งหนึ่งในการวนซ้ำทุกครั้ง แทนที่จะรวมรายการตามลำดับ ในรายการขนาดใหญ่ วิธีนี้มีประโยชน์จริงๆ

ชำระเงิน: การจำแนกต้นไม้การตัดสินใจ: ทุกสิ่งที่คุณจำเป็นต้องรู้

บทสรุป

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

หากคุณอยากเรียนรู้เกี่ยวกับวิทยาศาสตร์ข้อมูล ให้ลองดูประกาศนียบัตร PG ด้านวิทยาศาสตร์ข้อมูลของ IIIT-B และ upGrad ซึ่งสร้างขึ้นสำหรับมืออาชีพด้านการทำงานและเสนอกรณีศึกษาและโครงการมากกว่า 10 รายการ เวิร์กช็อปภาคปฏิบัติจริง การให้คำปรึกษากับผู้เชี่ยวชาญในอุตสาหกรรม 1- on-1 กับที่ปรึกษาในอุตสาหกรรม การเรียนรู้มากกว่า 400 ชั่วโมงและความช่วยเหลือด้านงานกับบริษัทชั้นนำ