java - 关于第一个索引值的搜索算法错误

Question

您好，我正在查看下面链接中关于此搜索算法的这篇文章，当我尝试运行它时，通过打印出您正在搜索的数字 (l) 的索引值，一切正常，但是如果您正在搜索的 number(l) 是数组中的第一个元素，那么它只打印 -1 而不是 0。此程序需要进行哪些更正？假设 int l = 3，那么它应该打印 0。

下面的代码来自这篇文章 jump search algorithm与亚历克斯温斯顿所述的更正。

我完全遵循了这篇维基文章 http://en.wikipedia.org/wiki/Jump_search 的内容发布关于该算法的实现

import java.math.*; 

public class  jamp  {

public  static int min(int a,int b) {
    return a<b?a:b;
}

public  static void main(String[]args) {
    int  a[]=new int[]{3,7,9,12,14,15,16,17,18};
    int l=14;                                            //lets say int l = 3;
    System.out.println(jumpsearch(a,a.length,l));
}

public static int jumpsearch(int a[],int n, int  l ) {
    int t=0;
    int b=(int)Math.sqrt(n);
    while (a[min(b,n)-1]<l){
        t=b;
        b=b+(int)Math.sqrt(n);
        if ( t>=n)  return  -1  ;
    }
    while (a[t]<l){
        t=t+1;
        if ( t==min(b,n))    
            return   -1  ;
        if ( a[t]==l)  {
            return t;
        }
    }
    return -1;            // if this is 0, then it works but if you search for a element that is not in the array then it still prints 0 which is incorrect
}
}

Answer 1

错误在于此部分:

  while (a[t]<l){
        t=t+1;
        if ( t==min(b,n))    
            return   -1  ;
        if ( a[t]==l)  {
            return t;
        }
 }

对于 l = 3 ，所以在第一个循环之后，t = 0和 a[t] == l , 所以 while 循环的条件 a[t] < l为false，所以你的程序直接返回-1而不进入循环。

您可以在进入此循环之前添加条件检查:

if(a[t] == l)
   return t;
while(a[t] < l){
  //the rest of your code.
}