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

การค้นแบบกระโดด () หรือในบางครั้งเรียกว่า การค้นแบบบล็อก () เป็นขั้นตอนวิธี สำหรับการค้นหาค่าที่สนใจภายในแถวลำดับที่มีการเรียงลำดับแล้ว
โดยจะทำการตรวจสอบข้อมูลในแถวลำดับทุก ๆ 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) ที่มีประสิทธิภาพเท่ากับ  แต่ก็มีประสิทธิภาพน้อยกว่า การค้นแบบทวิภาค (Binary Search) ที่มีประสิทธิภาพเท่ากับ 

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

 อ้างอิง 
 Jump Search
 Algorithm and Data Structures : Jump Search
 Jump Search(Divide and Conquer) : วิเคราะห์เวลาการทำงาน
 Source Code : ตัวอย่างโปรแกรม

 ดูเพิ่ม 
 การค้นแบบทวิภาค (Binary search)
 การค้นแบบเชิงเส้น (Linear search)

หมวดหมู่:ขั้นตอนวิธีการค้นหา