JetBrains Academy: Jump search in Java - Kamil-Jankowski/Learning-JAVA GitHub Wiki

JetBrains Academy: Jump search in Java

Print comparisons:

If you have an array of size N, how many comparisons do you need to perform to find each element of this array using jump search?

Given a number N, you should output N numbers - a number of comparisons you need to perform if the element you search for happens to be on this place.

import java.util.*;
import java.util.stream.Collectors;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int size = scanner.nextInt();
        
        System.out.println(printComparisons(size));
        
    }
    
    public static String printComparisons(int size) {
        int jump = (int) Math.sqrt(size);
        int[] array = new int[size];

        // jumping search steps:
        for (int i = 0; i < size; i++) {
            // comparisons at jump indexes
            if (i % jump == 0) {
                array[i] = 1 + i / jump;
            // comparison at the last index (if last jump block is smaller than jump size)
            } else if (i == size - 1) {
                array[i] = 1 + i / jump + 1;
            }
        }

        int rightBorder = 0;
        // backward linear search steps:
        for (int i = 0; i < size; i++) {
            // for normal jump blocks
            if (i % jump == 0 && i != 0) {
                rightBorder = array[i];
                for (int j = 1; j < jump; j++) {
                    array[i - j] = rightBorder + j;
                }
            // for last jump block
            } else if (i == size - 1) {
                rightBorder = array[i];
                int lastJump = (size - 1) % jump;
                for (int j = 1; j < lastJump; j++) {
                    array[i - j] = rightBorder + j;
                }
            }
        }

        return Arrays.stream(array)
                     .mapToObj(Integer::toString)
                     .collect(Collectors.joining(" "));
    }
}

---

Find a block that may contain the target value:

Write a program that reads an ascending sorted array of integers and a single value. The program should find the first suitable block for this value according to the values of block borders.

We consider only a possibility to have the element according to its value and the values of block borders. We do not check the block actually contain the element.

Your algorithm should use principles of the jump search.

As a block size use the optimal value. The last block can have the smaller size.

Input data format: The first line contains the length of an input array, the second one consists of array elements, the last one has the target value.

Output data format: The program must output the left and the right indexes of the found block separated by space. If no any block could contain the value, output the string "-1".

import java.util.*;

class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        Integer.parseInt(scanner.nextLine()); // size of array
        int[] array = Arrays.stream(scanner.nextLine().split("\\s+"))
                            .mapToInt(Integer::parseInt)
                            .toArray();
        int value = Integer.parseInt(scanner.nextLine());
        
        System.out.println(findBlockBorders(array, value));
    }
    
    public static String findBlockBorders(int[] array, int value) {
        String blockBorders = "";
        int leftBorder = 0;
        int rightBorder = -1;

        /* Calculating the jump length over array elements */
        int jump = (int) Math.sqrt(array.length);

        /* If array is empty, the element is not found */
        if (array.length == 0) {
            return "-1";
        }

        /* Finding a block where the element may be present */
        while (rightBorder < array.length - 1) {

            /* Calculating the right border of the following block */
            rightBorder = Math.min(array.length - 1, rightBorder + jump);

            if (array[rightBorder] >= value) {
                blockBorders = leftBorder + " " + rightBorder;
                break; // Found a block that may contain the target element
            }

            leftBorder = rightBorder + 1; // update the left border for the next block
        }

        /* If the last block is reached and it cannot contain the target value => not found */
        if (rightBorder == array.length - 1 && value > array[rightBorder]) {
            return "-1";
        }

        return blockBorders;
    }
}

---

Count comparisons:

Count how many comparisons you need to do to determine the index of the element, or to determine that this element is not in the array.

You need to use the jump search algorithm described in the theory.

The first line contains the length of an input array, the second one consists of array elements, the last one has the target value.

import java.util.*;

public class Main {
    
    static int count = 0;
    
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        Integer.parseInt(scanner.nextLine());
        int[] array = Arrays.stream(scanner.nextLine().split("\\s+"))
                            .mapToInt(Integer::parseInt)
                            .toArray();
        int value = Integer.parseInt(scanner.nextLine());
        
        System.out.println(countComparisons(array, value));
    }
    
    public static int countComparisons(int[] array, int value) {
        count = 0;

        int currentRight = 0; // right border of the current block
        int prevRight = 0; // right border of the previous block

        /* Check the first element */
        count++; // count comparison
        if (array[currentRight] == value) {
            return count;
        }

        /* Calculating the jump length over array elements */
        int jumpLength = (int) Math.sqrt(array.length);

        /* Finding a block where the element may be present */
        while (currentRight < array.length - 1) {

            /* Calculating the right border of the following block */
            currentRight = Math.min(array.length - 1, currentRight + jumpLength);

            if (array[currentRight] >= value) {
                break; // Found a block that may contain the target element
            }

            prevRight = currentRight; // update the previous right block border
            count++; // count comparison
        }

        /* If the last block is reached and it cannot contain the target value => not found */
        if (currentRight == array.length - 1 && value > array[currentRight]) {
            return count;
        }

        /* Doing linear search in the found block */
        return backwardSearch(array, value, prevRight, currentRight);
    }

    public static int backwardSearch(int[] array, int target, int leftExcl, int rightIncl) {
        for (int i = rightIncl; i > leftExcl; i--) {
            count++; // count comparison
            if (array[i] == target) {
                break;
            } else if (array[i] < target) {
                break;
            }
        }
        return count;
    }
}

---