เนื้อหา

• แผนภูมิเปรียบเทียบ
• ความหมายของการค้นหาเชิงเส้น
• ความหมายของการค้นหาแบบไบนารี
• ข้อสรุป

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

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

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

1. แผนภูมิเปรียบเทียบ
2. คำนิยาม
3. ความแตกต่างที่สำคัญ
4. ข้อสรุป

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

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

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

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

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

อย่างมีประสิทธิภาพ ของการค้นหาเชิงเส้น

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

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

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

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

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

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

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

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

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

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

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

#include ถือเป็นโมฆะ main () {int i, beg, end, middle, n, search, array; f ("ป้อนจำนวนองค์ประกอบ n"); scanf ( "% d", & n); f ("ป้อน% d หมายเลข n", n); สำหรับ (i = 0; i <n; i ++) scanf ("% d", & อาร์เรย์); f ("ป้อนหมายเลขที่จะค้นหา n"); scanf ("% d", & ค้นหา); ขอ = 0; end = n - 1; กลาง = (ขอ + จบ) / 2; ในขณะที่ (beg <= end) {ถ้า (array <search) beg = middle + 1; หากไม่พบ (array == search) {f ("การค้นหาสำเร็จ n% d พบที่ตำแหน่ง% d. n", ค้นหา, กลาง + 1); ทำลาย; } else end = middle - 1; กลาง = (ขอ + จบ) / 2; } ถ้า (beg> end) f ("ค้นหาไม่สำเร็จ!% d ไม่ปรากฏในรายการ n", ค้นหา); getch (); }

1. การค้นหาเชิงเส้นมีความสำคัญในลักษณะวนซ้ำและใช้วิธีการเรียงตามลำดับ ในทางกลับกันการค้นหาแบบไบนารี่ใช้วิธีแบ่งและพิชิต
2. ความซับซ้อนของเวลาของการค้นหาเชิงเส้นคือ O (N) ในขณะที่การค้นหาแบบไบนารีมี O (บันทึก₂N)
3. เวลากรณีที่ดีที่สุดในการค้นหาเชิงเส้นสำหรับองค์ประกอบแรกคือ O (1) ในทางตรงกันข้ามการค้นหาแบบไบนารี่นั้นมีไว้สำหรับองค์ประกอบกลางนั่นคือ O (1)
4. ในการค้นหาเชิงเส้นกรณีที่เลวร้ายที่สุดสำหรับการค้นหาองค์ประกอบคือจำนวน N การเปรียบเทียบ ในทางตรงกันข้ามมันเป็นบันทึก₂จำนวนการเปรียบเทียบสำหรับการค้นหาแบบไบนารี
5. การค้นหาเชิงเส้นสามารถดำเนินการในอาร์เรย์เช่นเดียวกับในรายการที่เชื่อมโยงในขณะที่การค้นหาแบบไบนารีไม่สามารถดำเนินการโดยตรงในรายการที่เชื่อมโยง
6. ดังที่เราทราบการค้นหาแบบไบนารี่ต้องการอาเรย์ที่เรียงลำดับซึ่งเป็นเหตุผลมันต้องการการประมวลผลเพื่อแทรกในตำแหน่งที่เหมาะสมเพื่อรักษารายการที่เรียง ในการค้นหาเชิงเส้นในทางตรงกันข้ามไม่จำเป็นต้องมีองค์ประกอบเรียงดังนั้นองค์ประกอบจะถูกแทรกได้อย่างง่ายดายในตอนท้ายของรายการ
7. การค้นหาแบบเชิงเส้นใช้งานง่ายและไม่จำเป็นต้องมีองค์ประกอบที่สั่งซื้อใด ๆ ในทางตรงกันข้ามอัลกอริธึมการค้นหาแบบไบนารี่นั้นเป็นเรื่องที่ยุ่งยากและมีการจัดเรียงองค์ประกอบตามลำดับ

ข้อสรุป

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

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