(탐색알고리즘) 순차 탐색(Sequential Search)

순차 탐색(Sequential Search)

순차 탐색(Sequential Search)은 탐색할 데이터가 모인 집합이 있으면 집합의 처음부터 끝까지 집합의 원소들을 비교하여 원하는 데이터를 찾는 알고리즘입니다.

순차 탐색은 데이터를 조작하지 않아 쉽게 구현할 수 있지만 비효율적인 탐색 방법입니다. 단방향으로 탐색을 진행하기 때문에 선형탐색(Linear Search)라고 부릅니다.

-------------> 순서대로 탐색

7

14

2

10

11

16

순차 탐색은 알고리즘이 단순하여 구현하기 정말 쉽고 정렬되어 있지 않은 데이터의 집합에서 평균적으로 (n+1)/2번의 비교를 거치고, 최악의 경우 n번의 거칩니다.

복잡도는 O(n)입니다. 아래 예제 코드와 함께 간단한 주석을 첨부하였으니 확인하시면 됩니다.

순차 탐색알고리즘은 배열뿐만아니라 자바의 ArrayList, LinkedList 등등 자료구조에도 적용할 수 있습니다.

package search;

import java.util.Scanner;

public class SequentialSearch {
    public static void main(String[] args) {
        int[] dataArray = { 7, 14, 2, 10, 11, 16 };

        System.out.println("검색할 데이터를 입력하세요");
        Scanner scan = new Scanner(System.in); 
        int search = Integer.parseInt(scan.nextLine().trim()); //데이터를 입력받습니다.
      
        int result = sequentialSearch(dataArray, search);

        if(result == -1)
            System.out.println("데이터를 찾지 못하였습니다");
        else
            System.out.println("데이터의 위치는 " + result + "번 째입니다.");
    }

    public static int sequentialSearch(int[] arr, int search) {
        for (int i = 0; i < arr.length; i++) { //순서대로 비교하기 위해 배열의 크기만큼 반복합니다.
            if (arr[i] == search) //비교할 데이터가 배열에 있으면 배열의 위치를 return하고, 없다면 -1을 return합니다.
                return i;
        }
        return -1;
    }

}