Linear Search (선형 탐색)

선형 탐색(linear search)은 순차 탐색(sequential search)이라고도 하는데, 주어진 데이터 집합에서 원하는 데이터를 처음부터 순차적으로 비교하면서 찾는 방법이다. 예를 들어 비유하면, 무작위로 모여진 명함 중에서 원하는 사람의 명함을 찾는 경우를 들 수 있다.

 

 

① 첫 번째 데이터인 15와 찾고자 하는 3이 같은지 비교하는데, 다르므로 다음으로 이동한다.

② 두 번째 데이터인 11과 찾고자 하는 3이 같은지 비교하는데, 다르므로 다음으로 이동한다.

③ 세 번째 데이터인 1과 찾고자 하는 3이 같은지 비교하는데, 다르므로 다음으로 이동한다.

④ 네 번째 데이터인 3과 찾고자 하는 3이 같은지 비교하는데, 같으므로 원하는 데이터를 찾고 탐색을 종료한다.

만약 마지막까지 원하는 데이터를 찾지 못하면 탐색 실패로 종료한다.

 

Java Code

import java.util.Scanner;

public class Linear {
    int arr[] = { 15, 11, 1, 3, 8 };
    int result;

    private int search(int input) {
        for (int i = 0; i < arr.length; i++) {
            if (input == arr[i]) {
                result = i;
                break;
            } else {
                result = -1;
                continue;
            }
        }
        return result;
    }

    public static void main(String[] args) {
        Linear linear = new Linear();
        Scanner sc = new Scanner(System.in);
        int input = sc.nextInt();
        sc.close();

        int result = linear.search(input);

        if (result == -1) {
            System.out.println("존재하지 않는 값입니다.");
        } else {
            System.out.println(result + "번 인덱스 값입니다.");
        }
    }
}

선형 탐색의 시간 복잡도는 O(n)이다.

 

[참조문서]
https://terms.naver.com/entry.naver?docId=2270439&cid=51173&categoryId=51173&expCategoryId=51173