使用 Java 的 DSA - 线性搜索

概述

线性搜索是一种非常简单的搜索算法。在这种类型的搜索中，会逐个对所有项目进行顺序搜索。检查每个项目，如果找到匹配项，则返回该特定项目，否则搜索将继续，直到数据收集结束。

算法

线性搜索(A:项目数组，n:项目总数，x:要搜索的项目)
步骤 1:将 i 设置为 1
步骤 2:如果 i > n 则转到步骤 7
步骤 3:如果 A[i] = x 则转到步骤 6
步骤 4:将 i 设置为 i + 1
步骤 5:转到步骤 2
步骤 6:打印在索引 i 处找到的元素 x 并转到步骤 8
步骤 7:打印未找到的元素
步骤 8:退出

演示程序

package com.tutorialspoint.simplesearch;

import java.util.Arrays;

public class LinearSearchDemo {

public static void main(String args[]){
        // 将进行线性搜索的项目数组。
        int[] sourceArray = {1,2,3,4,6,7,9,11,12,14,15,
                            16,17,19,33,34,43,45,55,66,76,88};
        System.out.println("输入数组:" +Arrays.toString(sourceArray));
        printline(50);
        //查找 1 的位置
        int location = find(sourceArray, 55);
        
        // 如果找到元素
      	if(location != -1)
         System.out.println("Element found at location: " +(location+1));
      	else
         System.out.println("Element not found.");

   }

   // 此方法进行线性搜索。 
   public static int find(int[] intArray, int data){
      int comparisons = 0;
      int index= -1;

      // 浏览所有项目
      for(int i=0;i<intArray.length;i++){
         // 计算所进行的比较次数
         comparisons++;
         // 如果找到数据，则中断循环 
         if(data == intArray[i]){
            index = i;
            break;
         }
      }
      System.out.println("Total comparisons made: " + comparisons);
      return index;
   }
   
   public static void printline(int count){
      for(int i=0;i <count-1;i++){
         System.out.print("=");
      }
         System.out.println("=");
   }
}

如果我们编译并运行上述程序，则会产生以下结果 −

Input Array: [1, 2, 3, 4, 6, 7, 9, 11, 12, 14, 15, 16, 17, 19, 33, 34, 43, 45, 55, 66, 76, 88]
==================================================
Total comparisons made: 19
Element found at location: 19