Jump search is a searching algorithm that works on sorted arrays. It is similar to binary search, but instead of dividing the array into two equal halves, it jumps or skips some elements based on a step size until it finds an element greater than or equal to the search key. Once the element is found, it performs a linear search between the previous and current positions to find the exact position of the key.
fun jumpSearch(arr: IntArray, key: Int): Int {
val n = arr.size
var step = kotlin.math.sqrt(n.toDouble()).toInt()
var prev = 0
// Find the block where the key is present
while (arr[kotlin.math.min(step, n) - 1] < key) {
prev = step
step += kotlin.math.sqrt(n.toDouble()).toInt()
if (prev >= n) {
return -1 // Key not found
}
}
// Perform a linear search in the block
while (arr[prev] < key) {
prev++
if (prev == kotlin.math.min(step, n)) {
return -1 // Key not found
}
}
return if (arr[prev] == key) prev else -1 // Return the index of the key, or -1 if not found
}The jumpSearch function takes two arguments: an array arr of integers and a search key key to look for. It returns the index of the key in the array, or -1 if it is not found.
The function first calculates the step size as the square root of the length of the array, and initializes the previous and current positions to 0. It then performs a while loop to find the block where the key is present by checking if the element at the current step size is less than the key. If it is, it jumps to the next block by adding the step size to the previous position and doubling the step size. If the previous position is greater than or equal to the length of the array, the key is not found and the function returns -1.
Once the block is found, the function performs a linear search within that block to find the exact position of the key by checking each element in the block starting from the previous position. If the previous position is equal to or greater than the current step size, or the end of the array, the key is not found and the function returns -1.
Finally, the function returns the index of the key if it is found, or -1 if it is not found.
fun main() {
val arr = intArrayOf(20,30,40,50,60,70,80,90)
val index = jumpSearch(arr, 30)
if (index != -1) {
println("Target found at index $index")
}
else {
println("Target not found in the array")
}
}
fun jumpSearch(arr: IntArray, key: Int): Int {
val n = arr.size
var step = kotlin.math.sqrt(n.toDouble()).toInt()
var prev = 0
// Find the block where the key is present
while (arr[kotlin.math.min(step, n) - 1] < key) {
prev = step
step += kotlin.math.sqrt(n.toDouble()).toInt()
if (prev >= n) {
return -1 // Key not found
}
}
// Perform a linear search in the block
while (arr[prev] < key) {
prev++
if (prev == kotlin.math.min(step, n)) {
return -1 // Key not found
}
}
return if (arr[prev] == key) prev else -1 // Return the index of the key, or -1 if not found
}