ดูต้นฉบับสำหรับ การค้นหาแบบกระโดด

'''การค้นแบบกระโดด''' ({{langx|en|jump search}}) หรือในบางครั้งเรียกว่า '''การค้นแบบบล็อก''' ({{langx|en|block search}}) เป็น[[ขั้นตอนวิธี]] สำหรับการค้นหาค่าที่สนใจภายในแถวลำดับที่มีการเรียงลำดับแล้ว
โดยจะทำการตรวจสอบข้อมูลในแถวลำดับทุก ๆ j ตัว โดยจะทำการตรวจสอบไปเรื่อย ๆ จนกว่าจะพบข้อมูลที่สนใจ ซึ่งวิธีนี้จะคล้ายกับ[[การค้นแบบเชิงเส้น]] (Linear Search)

การค้นหาแบบนี้จะได้ผลดีที่สุดเมื่อ j มีค่าเท่ากับ รากที่สองของ n เมื่อ n เป็นความยาวของแถวลำดับ

== รหัสเทียม ==

: '''ข้อมูลขาเข้า''' : แถวลำดับที่เรียงลำดับข้อมูลแล้ว มีความยาวเท่ากับ n และให้ s คือค่าที่เราสนใจ<br />
: '''ข้อมูลขาออก''' : จะส่งตำแหน่งของข้อมูลที่สนใจออกมา และถ้าหากไม่พบข้อมูลที่สนใจ จะไม่ส่งค่าอะไรกลับมา<br />
: ให้ a มีค่าเท่ากับ 0<br />
: ให้ b มีค่าเท่ากับ n<br />
: ทำงานไปเรื่อย ๆ เมื่อ ( (ค่าที่น้อยกว่าระหว่าง b กับ n ) -1 < s) เป็นจริง{<br />
:: a = b <br />
:: b = b + √n<br />
: ถ้า a มากกว่าหรือเท่ากับ n ให้ออกจากวงวน และไม่คืนค่าอะไรออกมา<br />
: }<br />
: ทำงานไปเรื่อย ๆ เมื่อ ( ถ้า a น้อยกว่า s) เป็นจริง{<br />
:: a = a + 1<br />
: ถ้า a เท่ากับ ค่าที่น้อยกว่าระหว่าง b กับ n ให้ออกจากวงวนและไม่คืนค่าอะไรออกมา<br />
: }<br />
: ถ้า a = s ก็ให้ทำการคืนตำแหน่ง a ออกไป<br />
: ถ้าไม่เช่นนั้นให้ ไม่ต้องคืนค่าอะไรออกมา<br />
<br />

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

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

== อ้างอิง ==
* [http://xlinux.nist.gov/dads/HTML/jumpsearch.html Jump Search]
* [https://ece.uwaterloo.ca/~ece250/Algorithms/Searching/Jump_search/ Algorithm and Data Structures : Jump Search]{{ลิงก์เสีย|date=กันยายน 2021 |bot=InternetArchiveBot |fix-attempted=yes }}
* [http://www.cs.gsu.edu/~cscskp/Algorithms/search/node3.html#SECTION00011100000000000000 Jump Search(Divide and Conquer) : วิเคราะห์เวลาการทำงาน]
* [https://ece.uwaterloo.ca/~ece250/Algorithms/Searching/Jump_search/src/ Source Code : ตัวอย่างโปรแกรม]{{ลิงก์เสีย|date=กันยายน 2021 |bot=InternetArchiveBot |fix-attempted=yes }}

== ดูเพิ่ม ==
* [[การค้นแบบทวิภาค]] ([[:en:Binary search|Binary search]])
* [[การค้นแบบเชิงเส้น]] ([[:en:Linear search|Linear search]])

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