ความแตกต่างระหว่างการค้นหาเชิงเส้นและการค้นหาแบบไบนารี

2019

การค้นหาเชิงเส้นและการค้นหาแบบไบนารีเป็นสองวิธีที่ใช้ในอาร์เรย์สำหรับ การค้นหา องค์ประกอบ การค้นหาเป็นกระบวนการค้นหาองค์ประกอบภายในรายการองค์ประกอบที่จัดเก็บในลำดับใด ๆ หรือแบบสุ่ม

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

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

แผนภูมิเปรียบเทียบ

พื้นฐานสำหรับการเปรียบเทียบ	การค้นหาเชิงเส้น	ค้นหาแบบทวิภาค
ความซับซ้อนของเวลา	บน)	O (บันทึก `₂` N)
เวลากรณีที่ดีที่สุด	องค์ประกอบแรก O (1)	องค์ประกอบศูนย์ O (1)
ข้อกำหนดเบื้องต้นสำหรับอาร์เรย์	ไม่จำเป็น	อาร์เรย์ต้องเรียงตามลำดับ
กรณีที่เลวร้ายที่สุดสำหรับจำนวนองค์ประกอบ N	ต้องมีการเปรียบเทียบ	สามารถสรุปได้หลังจากบันทึกเพียง `₂` N การเปรียบเทียบ
สามารถดำเนินการได้	รายการ Array and Linked	ไม่สามารถนำไปใช้โดยตรงในรายการที่เชื่อมโยง
แทรกการดำเนินการ	แทรกได้อย่างง่ายดายในตอนท้ายของรายการ	ต้องการการประมวลผลเพื่อแทรกในตำแหน่งที่เหมาะสมเพื่อรักษารายการที่เรียงลำดับ
ประเภทอัลกอริทึม	ซ้ำในธรรมชาติ	แบ่งและพิชิตในธรรมชาติ
ความมีประโยชน์	ใช้งานง่ายและไม่จำเป็นต้องมีองค์ประกอบที่สั่งซื้อใด ๆ	ควรจัดระเบียบอัลกอริธึมและองค์ประกอบที่ยุ่งยากหากต้องการ
สายของรหัส	น้อยกว่า	มากกว่า

ความหมายของการค้นหาเชิงเส้น

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

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

ประสิทธิภาพ ของการค้นหาแบบเชิงเส้น

การใช้เวลาหรือจำนวนการเปรียบเทียบในการค้นหาบันทึกในตารางการค้นหาจะกำหนดประสิทธิภาพของเทคนิค หากบันทึกที่ต้องการอยู่ในตำแหน่งแรกของตารางการค้นหาจะมีการเปรียบเทียบเพียงรายการเดียวเท่านั้น เมื่อบันทึกที่ต้องการคือบันทึกสุดท้ายจะต้องมีการเปรียบเทียบ หากบันทึกนั้นปรากฏที่ใดที่หนึ่งในตารางการค้นหาโดยเฉลี่ยจำนวนการเปรียบเทียบจะเป็น (n + 1/2) ประสิทธิภาพของเคสที่แย่ที่สุดของเทคนิคนี้คือ O (n) หมายถึงลำดับของการดำเนินการ

C โปรแกรม ค้นหาองค์ประกอบด้วยเทคนิคการค้นหาเชิงเส้น

 #include #include เป็นโมฆะ main () {int a [100], n, i, รายการ, loc = -1; clrscr (); printf ("\ n ใส่จำนวนองค์ประกอบ:"); scanf ("% d", & n); printf ("ป้อนตัวเลข: \ n"); สำหรับ (i = 0; i <= n-1; i ++) {scanf ("% d", & a [i]); } printf ("\ n ป้อนหมายเลขที่จะค้นหา:"); scanf ("% d", & รายการ); สำหรับ (i = 0; i = 0) {printf ("\ n% d อยู่ในตำแหน่ง% d:", รายการ, loc + 1); } else {printf ("\ n ไม่มีรายการ"); } getch (); }

ความหมายของการค้นหาแบบไบนารี

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

ตรรกะที่อยู่เบื้องหลังเทคนิคนี้ได้รับด้านล่าง:

ก่อนอื่นให้ค้นหาองค์ประกอบกลางของอาร์เรย์
องค์ประกอบกลางของอาร์เรย์เปรียบเทียบกับองค์ประกอบที่จะค้นหา

มีสามกรณีที่อาจเกิดขึ้น:

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

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

C โปรแกรม เพื่อค้นหาองค์ประกอบด้วยเทคนิคการค้นหาแบบไบนารี

 #include void main () {int i, beg, end, middle, n, ค้นหา, array [100]; printf ("ป้อนจำนวนองค์ประกอบ \ n"); scanf ( "% d", & n); printf ("ป้อน% d หมายเลข \ n", n); สำหรับ (i = 0; i <n; i ++) scanf ("% d", & อาร์เรย์ [i]); printf ("ป้อนหมายเลขที่จะค้นหา \ n"); scanf ("% d", & ค้นหา); ขอ = 0; end = n - 1; กลาง = (ขอ + จบ) / 2; ในขณะที่ (ขอ <= end) {ถ้า (อาร์เรย์ [กลาง] ปลาย) printf ("การค้นหาไม่สำเร็จ!% d ไม่ปรากฏในรายการ \ n", ค้นหา); getch (); }

ความแตกต่างที่สำคัญระหว่างการค้นหาเชิงเส้นและการค้นหาแบบไบนารี

ข้อสรุป

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

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