Page 45 - โครงสร้างข้อมูลและขั้นตอนวิธี
P. 45
ขั้นตอนว ิธีการค ้นหาข ้อมูล 15-35
เรอ่ื งท ่ี 15.2.1
การค น้ หาข ้อมูลแ บบก ระโดด
โดยท ั่วไปแ ล้วส �ำหรับข ้อมูลท ี่ม ีก ารจ ัดเรียงไวแ้ ล้ววิธีก ารค ้นหาแ บบล �ำดับเป็นว ิธกี ารท ี่มีประสิทธิภาพไมด่ ีน ัก
เพราะว่าต้องตรวจสอบสมาชิกแต่ละตัวก่อนถึงสมาชิกท่ีต้องการ ซึ่งเป็นท่ีทราบกันดีอยู่แล้วว่าสมาชิกของอาร์เรย์
ท่ีมีการเรียงตัวกันอยู่แล้วนั้น ไม่จ�ำเป็นต้องตรวจสอบสมาชิกทุกตัว การค้นหาแบบกระโดด (jump search)
ตรวจสอบสมาชิกของอาร์เรย์ ถ้าค่าน้อยกว่าค่าของข้อมูลที่สืบค้น ก็จะข้ามการตรวจสอบสมาชิกบางตัวโดยการข้าม
หรือกระโดดไปข้างหน้าและตรวจสอบค่าของสมาชิกตรงนั้นกับข้อมูลท่ีสืบค้น ถ้าค่าปัจจุบันมีค่ามากกว่าค่าท่ีสืบค้น
ก็จะทราบได้ว่าข้อมูลที่ต้องการค้นหาอยู่ระหว่างค่าท่ีตรวจสอบก่อนหน้านี้กับค่าปัจจุบัน ถ้าค่าของปัจจุบันน้อยกว่า
ค่าท่ีสืบค้น ก็ก ระโดดไปข้างหน้าและท�ำการต รวจสอบอีกคร้ัง ถ้ายังไม่ใช่ก็ท�ำซ้�ำ ซึ่งระยะการกระโดดน ั้นก �ำหนดให้เป็น
ค่า k โดยก ารตรวจส อบนั้นเป็นด ังนี้
คร้ังท ่ี 1 สมาชิกตัวแ รก
ครั้งท่ี 2 สมาชิกต ัวท ี่ k
ครั้งท่ี 3 สมาชิกต ัวท ี่ 2k
… k k
k
ภาพที่ 15.8 ชว่ งก ระโดดข องการเปรยี บเทียบ
ซึ่งหลังจากการที่กระโดดจนได้ช่วงที่ต้องการแล้วการตรวจสอบหาค่าท่ีต้องการในข้ันตอนต่อไปจะเป็น
การค ้นหาแ บบล �ำดับ
การเลอื กค า่ ท่จี ะกระโดดหรอื ข้าม
กำหนดให้ k เป็นค่าท่ีจะกระโดดหรือข้าม ถ้าให้ k มีค่าเป็น 1 วิธีการนี้จะเหมือนกับการค้นหาแบบล�ำดับ
ปัญหาคือจะก�ำหนดค่า k เป็นเท่าใดถึงจะเหมาะสม
สุดท้ายค ส่าข�ำอหงรสับมคา่าชkิกมใาดกๆกวน่า้ันค ่าใทน่ีตก้อรณงกีทารี่แหยา่ทจี่สะุดมวีกิธาีกรเาปรรนียี้จบะเกทรียะบโดอ ดีกทไม้ัง่เหกมินดk-nk1
คร้ัง และถ้าการตรวจสอบค่าคร้ัง
ครั้ง
