顺序查找是唯一能在未排序数据中查找给定值的算法。算法通常从第一个元素开始,遍历整个数组或列表,直至找到待查找的值位置。算法最后会返回找到元素的索引,或是无法作为索引的-1以代表没有找到。以下是一个AP计算机顺序查找的示例代码。

public class ArraySearcher
{

   /** Finds the index of a value in an array of integers.
     * @param elements an array containing the items to be searched.
     * @param target the item to be found in elements.
     * @return an index of target in elements if found; -1 otherwise.
     */
   public static int sequentialSearch(int[] elements, int target)
   {
     for (int j = 0; j < elements.length; j++)
     {
       if (elements[j] == target)
       {
         return j;
       }
     }
     return -1;
   }

   public static void main(String[] args)
   {
     int[] numArray = {3, -2, 9, 38, -23};
     System.out.println("Tests of sequentialSearch");
     System.out.println(sequentialSearch(numArray,3));
     System.out.println(sequentialSearch(numArray,9));
     System.out.println(sequentialSearch(numArray,-23));
     System.out.println(sequentialSearch(numArray,99));
   }

}


0:00

Which will cause the longest execution of a sequential search looking for a value in an array of integers?

当找不到值时,顺序查找耗时最长,找不到元素的话必然是要遍历整个数组或列表的。
4

Which will cause the shortest execution of a sequential search looking for a value in an array of integers?

当待查找值是数组的第一个元素时,在第一轮循环就找到并返回了,顺序查找耗时最短。
1

当然,你可以使用顺序查找来查找字符串。但此时务必用equals而非==。对于字符串而言,==返回的是两个变量是否指向同一个字符串object,equals才在字符的长度和顺序都一致时会返回true

public class SearchTest
{

   public static int sequentialSearch(String[] elements, String target)
   {
      for (int j = 0; j < elements.length; j++)
      {
         if (elements[j].equals(target))
         {
            return j;
         }
     }
     return -1;
   }

   public static void main(String[] args)
   {
      String[] arr1 = {"blue", "red", "purple", "green"};

      // test when the target is in the array
      int index = sequentialSearch(arr1,"red");
      System.out.println(index);

      // test when the target is not in the array
      index = sequentialSearch(arr1,"pink");
      System.out.println(index);
   }
}

陈 欣

AADPS创始人

发表评论