การค้นหาแบบกระโดด

การค้นแบบกระโดด (อังกฤษ: 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 มากกว่าหรือเท่ากับ n ให้ออกจากวงวน และไม่คืนค่าอะไรออกมา

}

ทำงานไปเรื่อย ๆ เมื่อ ( ถ้า a น้อยกว่า s) เป็นจริง{

a = a + 1

ถ้า a เท่ากับ ค่าที่น้อยกว่าระหว่าง b กับ n ให้ออกจากวงวนและไม่คืนค่าอะไรออกมา

}

ถ้า a = s ก็ให้ทำการคืนตำแหน่ง a ออกไป

ถ้าไม่เช่นนั้นให้ ไม่ต้องคืนค่าอะไรออกมา

ประสิทธิภาพการทำงาน

การค้นหาแบบกระโดด (Jump Search) หากใช้ค่าที่ดีที่สุดในการกระโดดค้นหา คือ √n เมื่อ n เป็นความยาวของแถวลำดับ แล้ว จะมีประสิทธิภาพเท่ากับ O(√n) ซึ่งดีกว่าการค้นแบบเชิงเส้น (Linear Search) ที่มีประสิทธิภาพเท่ากับ $O\left(n\right)$ แต่ก็มีประสิทธิภาพน้อยกว่า การค้นแบบทวิภาค (Binary Search) ที่มีประสิทธิภาพเท่ากับ $O\left(\log n\right)$

เราสามารถเพิ่มประสิทธิภาพการทำงานได้โดยการทำการค้นแบบกระโดดหลายระดับในแถวลำดับย่อย โดยสำหรับ k ระดับของการค้นแบบกระโดด ที่มีบล็อกขนาด m ที่ l ระดับ จะมีประสิทธิภาพการทำงานเท่ากับ O (n^(k-l))

อ้างอิง

ดูเพิ่ม