Please verify Jump searching algorithm

Question

Please verify jump searching algorithm that I have written and let me know if any bugs are present. I have tested it from my end, but still would like to get it verified for any missing corner scenarios.

class JumpSearch 
{
  public static void main(String[] args) 
  {
      int[] input = new int[] { 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610 , 670 };
      int target = 13;
      int output=-1;
      int step = (int) Math.floor(Math.sqrt(input.length));
      int lastIndex = input.length-1;
      int index=step; //directly jump to end of first block.
      System.out.println("step : " + step);
      System.out.println("start index : " + index);
      System.out.println("lastIndex : " + lastIndex);

      boolean jumpBlocks = true , endOfInput=false;;
        while(jumpBlocks)
        {
          if(target <= input[index])
          {
            int previousIndex = (index-step);
            System.out.println("previous index : " + previousIndex);
            for(int a=index ; a >= previousIndex ; a--)
            {
              if(input[a] == target)
              {
                output=a;
                break;
              }
            }
            break;
          }
          else
          {
            if(endOfInput)
            {
              jumpBlocks = false;
            }
            else
            {
              index += step;  
              if(index >= lastIndex)
              {
                endOfInput=true;
                index = lastIndex;
              }
            }
          }
        }
      System.out.println("output : " + output);
  }
}

Welcome back to Stack Review, please confirm if your code is referring to Jump_search and include yours tests. — dariosicily
– dariosicily, Commented Oct 18, 2021 at 17:07

vnp · Accepted Answer · 2021-10-18 17:57:26Z

The sheer amount of breaks, and boolean controls, is an immediate red flag. It is a natural consequence of a decision to stuff everything into a single loop. Try to decompose the problem into a smaller chunks instead.

First, the for loop implements an important algorithm, on its own rights. Namely, linear search. Don't be shy, and factor it out into the function. At the very least, this would let you unit test it.

Next, notice that the if clause of target <= input[index] condition is executed at most once. Therefore, it doesn't belong to the while loop. The purpose of that loop is to find the block which potentially contains the target. This observation allows a simple decomposition, along the lines of

    int blockStart = findContainingBlock(input, target, step);
    if (blockStart == input.length) {
        return -1;
    }
    int blockEnd = min(blockStart + step, input.length);
    int index = linearSearch(blockStart, blockEnd, target);
    return index;

A side note about the linear search. The for loop is broken when the target == input[a]. You may as well break it when target > input[a]: there is no point to search any further. It means that

    for (int a=index ; a >= previousIndex && target <= input[a]; a--)

expresses the goals more clearly.

Besides clarity, notice that every block, except the very first one, has a natural sentinel: we are guaranteed that the last value of the previous block is less than the target. It means that the for loop doesn't need to test for a >= previousIndex at all:

    for (int a=index ; target <= input[a]; a--)

works, and has twice as few comparisons.

Dealing with the first block is also easy: before even looking for a suitable block, test whether the target could be there at all.

    if (target < input[0]) {
        return -1; // target is definitely not there.
    }

Now the first block is not special.

Stack Exchange Network

Please verify Jump searching algorithm

1 Answer 1

You must log in to answer this question.

Hot Network Questions

Please verify Jump searching algorithm

1 Answer 1

You must log in to answer this question.

Related

Hot Network Questions