Page 32 - โครงสร้างข้อมูลและขั้นตอนวิธี
P. 32
15-22 โครงสร้างข้อมูลและข ั้นตอนวิธี
4.3 กรณที ว่ั ไป
กรณีน ี้ข้อมูลท ี่ต ้องการค ้นหาม ีค่าอยู่ระหว่างต �ำแหน่งแรกแ ละต �ำแหน่งส ุดท้ายในอ าร์เรย์เช่น
ข้อมูลที่ต้องการค้นหา คือ 16
ข้อมูล 1 7 15 16 23 32 n + 1
2
การค ้นหาล ักษณะน ี้จะใช้ก ารเปรียบเทียบโดยเฉลี่ย ดังน ้ัน ป ระสิทธิภาพเชิงเวลาเท่ากับ O(n)
5. การน�ำ ข น้ั ตอนว ิธกี ารค้นหาข้อมลู แบบเรยี งล�ำ ดับไปป ระยุกตใ์ ชง้ าน
ส�ำหรับก ารห าค ่ามากส ุดห รือน ้อยส ุดในก รณีท ่ีข้อมูลม ีการจัดเรียงแล้วน ั้นเป็นป ัญหาท ี่ง ่ายเน่ืองจากข ้อมูลจ ะ
เป็นสมาชิกตัวแ รกหรือตัวสุดท้ายเสมอซึ่งข ้ึนอ ยู่กับการจัดเรียงว่าจากค่าน้อยไปค่ามาก หรือจัดเรียงจากค่ามากไปค ่า
น้อย เช่น
5 24 33 43 68 73 90 91
ค่าน ้อยที่สุด i = 1 โดยท่ี A[1] = 5
5 24 33 43 68 73 90 91
ค่าม ากที่สุด i = 8 โดยที่ A[8] = 91
การค ้นหาเชิงเส้นนั้นยังสามารถน�ำไปหาข ้อมูลล�ำดับท่ีต ้องการ เช่น
5 24 33 43 68 73 90 91
ต้องการห าค ่าม ากท ่ีสุดล�ำดับที่ 5 ซ่ึงสามารถต อบได้เลย ค ือ A[5] ซึ่งเท่ากับ 68
กิจกรรม 15.1.3
1. ถ้าเปลย่ี น x < A[i] เปน็ x > A[i] ในบ รรทดั ท ี่ 6 ของฟ งั กช์ นั LinearSearch ผลจ ะเปน็ อ ยา่ งไร
2. การคน้ หาแ บบเรียงล�ำ ดับมีความเหมอื นแ ละแตกตา่ งกับการค้นหาแบบบรทู ฟอ ร์ซ อยา่ งไร
แนวต อบก จิ กรรม 15.1.3
1. ถา้ ข อ้ มลู ท สี่ บื คน้ ไมใ่ ชข่ อ้ มลู ต วั แ รกข องอ ารเ์ รย์ ฟงั กช์ นั LinearSearch จะไมม่ โี อกาสพ บข อ้ มลู เชน่
ขอ้ มลู 2, 3, 5, 9, 15, 21 ขอ้ มลู ทตี่ อ้ งการคน้ หาคอื x= 15 เมอื่ ฟงั กช์ นั ท�ำ งานถงึ บรรทดั ท่ี 6 จะเปรยี บเทยี บ x =15
กบั A[1] = 2 ตามเงื่อนไข x > A[i] ซ่ึงเป็นจ ริงและจ ะส ่งค า่ กลบั เป็น -1 ทันที
2. การค้นหาแบบเรียงลำ�ดับมีความเหมือนกับการค้นหาแบบบรูทฟอร์ซตรงที่การตรวจสอบสมาชิก
จะเรม่ิ ต งั้ แตต่ วั แ รกถ งึ ต วั ส ดุ ทา้ ย การค น้ หาท ง้ั ส องแ บบต า่ งก นั ต รงท เ่ี งอื่ นไขก ารส นิ้ ส ดุ ก ารท �ำ งาน การค น้ หาแ บบ
เรยี งล �ำ ดบั เพมิ่ เตมิ เงอื่ นไขซ งึ่ จ ะห ยดุ ค น้ หาท นั ทที ข่ี อ้ มลู ท ต่ี อ้ งการค น้ หานอ้ ยก วา่ ข อ้ มลู ณ ต�ำ แหนง่ ทเี่ ปรยี บเทยี บ
