Page 29 - โครงสร้างข้อมูลและขั้นตอนวิธี
P. 29
ขั้นตอนว ิธีก ารค้นหาข้อมูล 15-19
เรอ่ื งที่ 15.1.3
การค น้ หาข ้อมลู แบบเรยี งล �ำ ดบั
การค ้นหาแบบเรียงล�ำดับ (sequential search) หรือก ารค้นหาแ บบเชิงเส้น (linear search) มีข ั้นต อนวิธีท่ี
เข้าใจง่ายคล้ายกับการค้นหาข้อมูลแบบ Brute force ต่างกันตรงที่ข้อมูล ซึ่งการค้นหาแบบเรียงล�ำดับจัดการกับข้อมูล
ท่ีเรียงล �ำดับไว้แ ล้ว โดยล �ำดับข ้อมูลท ่ีน�ำมาใช้ในหน่วยน ี้เป็นการเรียงจ ากน ้อยไปมาก เช่น
5 9 11 12 23 43 54 61 64 69 76
โดยข้ันตอนวิธีจ ะเร่ิมท ่ีข ้อมูลแ รกข องร ายการ แล้วเปรียบเทียบค ่าท ีล ะตัวต ามล �ำดับ จนพ บค ่าท่ีต้องการ เช่น
ต้องการหาค่า 23 จะต้องเปรียบเทียบค่าจ ากก ารเร่ิมต้นท ่ี 5, 9, 11, 12 และ 23 ซึ่งจะเหมือนกับข้ันต อนว ิธีแบบ Brute
force อย่างไรก็ตามถ้าต้องการหาค่า 10 จะเปรียบเทียบกับค่าแรก คือ 5 จนถึงค่าที่ 3 คือ 11 เท่านั้นก็จะทราบว่า
ไม่พ บค่าที่ต ้องการ ซึ่งต ่างกับขั้นตอนวิธีแบบ Brute force ท่ีต้องหาจ นถึงส มาชิกตัวส ุดท้ายถ ึงจะทราบ
1. โครงสรา้ งข ้อมลู ของการค้นหาข้อมูลแบบเรียงล�ำ ดบั
ส�ำหรับโครงสร้างข้อมูลท่ีใช้ในการค้นหาแบบเรียงล�ำดับนั้นเป็นแบบอาร์เรย์หรือลิงค์ลิสต์ก็ได้โดยข้อมูล
ต้องมีการจัดเรียงมาก่อน
2. ข้ันตอนวิธีการคน้ หาข้อมูลแบบเรยี งลำ�ดับ
ข้ันต อนวิธี LinearSearch มีรายละเอียดดังนี้
ข้อมูลเข้าประกอบด้วย
อาร์เรย์ข้อมูลท ี่เรียงล�ำดับไว้แล้ว A
จ�ำนวนข้อมูลทั้งหมด
n
ค่าที่ต้องการค้นหา x
ข้อมูลท ี่ส ่งก ลับ
ถ้าพ บข ้อมูลที่สืบค้น ค่าที่ส่งกลับจะเป็นต�ำแหน่งของข้อมูลในอ าร์เรย์
ถ้าไม่พ บข ้อมูลท ี่ส ืบค้น ค่าที่ส่งก ลับจะเป็นต�ำแหน่งท ่ีไม่มีจริงในอาร์เรย์น่ันคือ -1
