การค้นหาแบบกระโดด
การค้นแบบกระโดด (อังกฤษ: jump search) หรือในบางครั้งเรียกว่า การค้นแบบบล็อก (อังกฤษ: block search) เป็นขั้นตอนวิธี สำหรับการค้นหาค่าที่สนใจภายในแถวลำดับที่มีการเรียงลำดับแล้ว โดยจะทำการตรวจสอบข้อมูลในแถวลำดับทุก ๆ j ตัว โดยจะทำการตรวจสอบไปเรื่อย ๆ จนกว่าจะพบข้อมูลที่สนใจ ซึ่งวิธีนี้จะคล้ายกับการค้นแบบเชิงเส้น (Linear Search)
การค้นหาแบบนี้จะได้ผลดีที่สุดเมื่อ j มีค่าเท่ากับ รากที่สองของ n เมื่อ n เป็นความยาวของแถวลำดับ
รหัสเทียม แก้
- ข้อมูลขาเข้า : แถวลำดับที่เรียงลำดับข้อมูลแล้ว มีความยาวเท่ากับ n และให้ s คือค่าที่เราสนใจ
- ข้อมูลขาออก : จะส่งตำแหน่งของข้อมูลที่สนใจออกมา และถ้าหากไม่พบข้อมูลที่สนใจ จะไม่ส่งค่าอะไรกลับมา
- ให้ a มีค่าเท่ากับ 0
- ให้ b มีค่าเท่ากับ n
- ทำงานไปเรื่อย ๆ เมื่อ ( (ค่าที่น้อยกว่าระหว่าง b กับ n ) -1 < s) เป็นจริง{
- a = b
- b = b + √n
- a = b
- ถ้า a มากกว่าหรือเท่ากับ n ให้ออกจากวงวน และไม่คืนค่าอะไรออกมา
- }
- ทำงานไปเรื่อย ๆ เมื่อ ( ถ้า a น้อยกว่า s) เป็นจริง{
- a = a + 1
- a = a + 1
- ถ้า a เท่ากับ ค่าที่น้อยกว่าระหว่าง b กับ n ให้ออกจากวงวนและไม่คืนค่าอะไรออกมา
- }
- ถ้า a = s ก็ให้ทำการคืนตำแหน่ง a ออกไป
- ถ้าไม่เช่นนั้นให้ ไม่ต้องคืนค่าอะไรออกมา
ประสิทธิภาพการทำงาน แก้
การค้นหาแบบกระโดด (Jump Search) หากใช้ค่าที่ดีที่สุดในการกระโดดค้นหา คือ √n เมื่อ n เป็นความยาวของแถวลำดับ แล้ว จะมีประสิทธิภาพเท่ากับ O(√n) ซึ่งดีกว่าการค้นแบบเชิงเส้น (Linear Search) ที่มีประสิทธิภาพเท่ากับ แต่ก็มีประสิทธิภาพน้อยกว่า การค้นแบบทวิภาค (Binary Search) ที่มีประสิทธิภาพเท่ากับ
เราสามารถเพิ่มประสิทธิภาพการทำงานได้โดยการทำการค้นแบบกระโดดหลายระดับในแถวลำดับย่อย โดยสำหรับ k ระดับของการค้นแบบกระโดด ที่มีบล็อกขนาด m ที่ l ระดับ จะมีประสิทธิภาพการทำงานเท่ากับ O (n^(k-l))