Continuing with the number guessing game — can we try a different approach for numbers 1 to 100?

If we start from the beginning and jump forward by 10 each time we don’t guess correctly, we keep going until the maximum value in our range becomes less than or equal to our guess, then we search backward to find the exact value. This approach can be more efficient when the target value is relatively small.

Concept

Jump Search: This algorithm is similar to binary search — the list being searched must also be sorted beforehand. During each search step, if the value isn’t found, it quickly jumps to the next segment using a fixed block size. Once the maximum boundary shrinks, it searches backward to find the value. If found, it returns the element’s index; otherwise, it returns -1.

The description above might be a bit complex, so let’s use the number guessing game as an example. Suppose we’re looking for the value 30:

• Step 1: index = 1, the target value is not 1, increment the index by 10.
• Step 2: index = 11, the target value is not 11, increment the index by 10.
• Step 3: index = 21, the target value is not 21, increment the index by 10.
• Step 4: index = 31, the target value is not 31, but we notice the target is smaller than 31, so we start searching backward, decrementing by 1.
• Step 5: index = 30, found the target! Return the index.

Complexity

• Time complexity: O(√n)
• Space complexity: O(1)

Examples

Go

package main

import (
    "fmt"
    "math"
)

func jumpSearch(list []int, target int) int {
    blockSize := int(math.Sqrt(float64(len(list))))

    i := 0
    for {
        if i > len(list) {
            return -1
        }

        if list[i] >= target {
            break
        }

        i += blockSize
    }

    for j := i; j > 0; j-- {
        if list[j] == target {
            return j
        }
    }

    return -1
}

func main() {
    fmt.Println(jumpSearch([]int{1, 2, 3, 4, 5}, 3)) // 2
    fmt.Println(jumpSearch([]int{1, 2, 3, 4, 5}, 6)) // -1
}

C#

class Algorithm
{
    public static int jumpSearch(int[] list, int target)
    {
        var blockSize = (int)Math.Sqrt(list.Length);

        var i = 0;
        while (true)
        {
            if (i > list.Length)
            {
                return -1;
            }

            if (list[i] >= target)
            {
                break;
            }

            i += blockSize;
        }

        for (var j = i; j > 0; j--)
        {
            if (list[j] == target)
            {
                return j;
            }
        }

        return -1;
    }

    public static void Main(String[] args)
    {
        Console.WriteLine(jumpSearch(new int[] {1, 2, 3, 4, 5}, 3)); // 2
        Console.WriteLine(jumpSearch(new int[] {1, 2, 3, 4, 5}, 6)); // -1
    }
}

Feel free to leave a comment on my blog. Your feedback motivates me to keep writing. Thank you for reading, and let’s grow together to become better versions of ourselves.