Page 44 - โครงสร้างข้อมูลและขั้นตอนวิธี
P. 44
15-34 โครงสร้างข้อมูลและข ั้นต อนวิธี
ความน�ำ
ขั้นต อนวิธีการค้นหาในต อนที่ 15.1 เป็นร ูปแบบท่ีแ พร่ห ลายแ ละร ู้จักกันเป็นอย่างด ี ท้ัง 3 รูปแบบ
- การค้นหาแ บบบรูทฟอ ร์ซ สืบค้นเรียงรายตัวจากข้อมูลท ี่ยังไม่ได้เรียงล �ำดับจ นกว่าจะพบข้อมูลท่ีส ืบค้น
- การค ้นหาแ บบเรียงล �ำดับ สืบค้นข ้อมูลเรียงต ัวจ ากข ้อมูลท ่ีจ ัดเรียงม าแล้วซ ่ึงท�ำให้เงื่อนไขก ารไม่พ บข ้อมูล
ตรวจพบได้เร็วก ว่า
- การค้นหาแบบทวิภาคที่สืบค้นข้อมูลโดยการลดจ�ำนวนที่สืบค้นลงคร้ังละคร่ึงหนึ่ง โดยการเปรียบเทียบ
ค ่าว ่ามากกว่าห รือน ้อยก ว่า
ส�ำหรับเนื้อหาในตอนน้ีเป็นขั้นตอนวิธีการค้นหาท่ีค ล้ายกับการค้นหาแบบทวิภาคต่างกันตรงที่ก ารตรวจสอบ
ข้อมูลน้ันไม่ได้ต รวจสอบข ้อมูลจากต �ำแหน่งตรงกลางทุกครั้งไปแ ต่จ ะตรวจส อบต ามร ูปแบบดังนี้
- การค้นหาแบบกระโดด ใช้ประโยชน์จากข้อมูลสมาชิกของอาร์เรย์ท่ีมีการเรียงตัวกัน ซึ่งไม่จ�ำเป็นต้อง
ตรวจสอบสมาชิกท ุกตัว เมื่อสมาชิกของอ าร์เรย์ได้ร ับก ารต รวจส อบ ถ้าค่าน ้อยกว่าค ่าข องข ้อมูลท่ีส ืบค้น สามารถที่จะ
ข้ามการตรวจสอบสมาชิกบางตัวโดยการข้ามหรือกระโดดไปข้างหน้าและตรวจสอบค่าของสมาชิกตรงนั้นกับข้อมูล
ที่สืบค้น ถ้าค่าปัจจุบันมีค่ามากกว่าค่าที่สืบค้น หมายถึงข้อมูลท่ีต้องการค้นหาอยู่ระหว่างค่าท่ีตรวจสอบก่อนหน้านี้
กับค่าปัจจุบัน ถ้าค่าปัจจุบันน้อยกว่าค่าที่สืบค้นเราต้องกระโดดไปข้างหน้าและท�ำการตรวจอีก ถ้ายังไม่ใช่อีกก็ท�ำซํ้า
อีกซ่ึงก ารกร ะโดดน ้ันก �ำหนดให้เป็นค ่า โดยค่า k ท่ีเหมาะสมคือ n ซึ่ง n คือจ�ำนวนข้อมูล
- การค้นหาแบบการประมาณค่าในช่วง คล้ายกับการค้นหาแบบกระโดดที่ไม่ใช้วิธีการตรวจสอบสมาชิกท่ี
เรียงชิดติดกันแต่จะใช้สูตรในการค�ำนวณหาต�ำแหน่งท่ีตรวจสอบคร้ังต่อไป ซึ่งวิธีการน้ีพิจารณาจากข้อเท็จจริงที่ว่า
ข้อมูลมีการจัดเรียงอยู่แล้ว และสมมติฐานว่าข้อมูลมีการเพิ่มขึ้นแบบเชิงเส้น ตลอดจนการใช้ประโยชน์จากค่าของ
ข้อมูลที่สืบค้น ซ่ึงวิธีการค้นหาแบบการประมาณค่าในช่วงน้ีจะลอกเลียนแบบการค้นหาช่ือจากสมุดโทรศัพท์ ท่ีผู้ใช้
ประมาณค่าว่าช่ือท่ีต้องการหาน่าจะอยู่ท่ีหน้าใดแล้วเปิดไปยังหน้านั้น ส�ำหรับข้ันตอนวิธีนั้นการประมาณต�ำแหน่งใช้
สูตรที่ประยุกต์ใช้วิธีก ารหาค ่าของสมการเส้นตรง
- การค้นหาแบบฟิโบนักซีนั้นใช้แนวคิดแบบเดียวกับการค้นหาแบบทวิภาค แต่การแบ่งช่วงการค้นหาน้ัน
ใชต้ วั เลขฟิโบนกั ซแี ทนการแบง่ ครง่ึ สำ� หรบั การตรวจสอบนน้ั ยงั เปน็ ลกั ษณะเดยี วกนั คอื ตรวจสอบคา่ ถา้ นอ้ ยกวา่ ตรวจ
สอบค ่าท างซ า้ ยถ้าม ากกวา่ ต รวจส อบค า่ ท างข วา โดยก ารต รวจส อบค ร้ังต อ่ ไปจ ะต รวจส อบจ ากต ำ� แหน่งท ่ีตรงก ับต ัวเลข
ถัดไปของช ุดล �ำดับฟิโบนักซ ี
