[Algorithm] 선형 검색

 

이번글에서는 배열에서 어떤 값을 검색하는 알고리즘 중 선형 검색에 대해 정리해 보겠다.

 

선형 검색(linear search)은 순차 검색(sequential search)라고도 불린다.

 

선형 검색 알고리즘은 매우 단순하다.

 

---

 

크기 5인 배열에서 어떤 값을 찾는다고 가정하자.

 

 

 

 

그림처럼 배열 맨 처음부터 끝까지 순차적으로 배열의 요소와 찾는 값을 비교하면 된다.

 

 

 

 

 

즉 선형 검색 알고리즘의 종료 조건은 2가지이다.

 

1. 검색할 값을 찾는 경우

2. 검색할 값을 찾기 못하고 배열의 끝까지 지나는 경우

 

 

 

선형 검색의 단점은 배열의 크기 (데이터 양)가 커지면 반복문도 크기만큼 돌아갈 수 있으니 시간이 오래 걸리는 검색 알고리즘이다.

 

단순한 만큼 효율성이 안 좋다.

---

 

import java.util.Scanner;

public class Sequential {
    
    //선형 검색 알고리즘
    static int search(int[] arr, int size, int key) {
        for(int i=0; i<size; i++){
            if(arr[i]==key){
                return i;
            }
        }
        return -1;

    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        System.out.print("배열의 크기는?: ");
        int size = sc.nextInt();
        int[] arr = new int[size];
        
        for (int i = 0; i < size; i++) {
            System.out.print("arr[" + i + "]: ");
            arr[i] = sc.nextInt();
        }
        
        System.out.print("찾는 값은?: ");
        int key = sc.nextInt();

        int keyPosition = search(arr,size,key);

        if(keyPosition==-1){
            System.out.println("값을 찾지 못했습니다.");
        }else{
            System.out.println("arr["+keyPosition+"]에 존재합니다.");
        }
    }
}

 

 

 

 

 

---

 

 

 

선형 검색의 시간복잡도

 

최선의 경우

  검색 대상 (key 값)이 배열의 첫 번째인 경우

  O(1)

 

최악의 경우

  검색 대상이 배열의 마지막에 존재하는 경우

  O(n)

 

평균적인 경우

  검색 대상이 배열의 가운데쯤 있을 확률이 높다고 가정.

  O(n)

 

•   첫 번째 위치: 1번 비교
•   두 번째 위치: 2번 비교
•   세 번째 위치: 3번 비교
•   n번째 위치: n번 비교

  등차수열의 합 공식을 이용해 평균 비교 횟수는 다음과 같다.

 

평균 비교 횟수 = (n+1)/2

따라서 O(n)  (1/2은 무시)

  

  더 상세한 평균 시간 복잡도

배열의 크기가 5라고 가정하자.

 

 

 등차수열의 합 공식 적용

 

 

총 비교 횟수는 15번

 

이제 평균을 구하면 된다.

 

 

 

정리

배열의 크기가 5일 때, 평균적으로 3번 비교한다. 이는 입력 크기 n에 비례하므로 

시간복잡도는 O(n)

 

 

---

 

 

선형 검색의 종료 조건은 2가지이다. 배열에서 값을 찾았을 때와 배열 끝까지 도달해서 넘어갈 때.

종료 조건 검사 감소시켜 실행 속도를 늘릴 수 있다.

그 방법은 보초법이다.

 

 

---

 

 

보초법

  보초법 역시 간단하다. 찾고자 하는 값을 배열 마지막에 값을 복사해서 넣는다. 

  즉 배열의 선언할 때 보초를 넣을 공간까지 +1 해야 한다.

  배열의 찾고자 하는 값이 없다면 배열의 맨 마지막 보초에서 같은 요소를 발견하게 된다.

  단, 발견한 것은 보초이다.

 

 

import java.util.Scanner;

public class LinearSearch {

    static int find(int[] arr, int key, int size) {
        int i;
        arr[size] = key;
        for (i = 0; i < arr.length; i++) {
            if (arr[i] == key) break;
        }
        return i == size ? -1 : i;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.print("배열의 크기는: ");
        int size = sc.nextInt();
        int[] array = new int[size + 1];  //보초 자리를 위해 배열 크기 1 증가

        for (int i = 0; i < size; i++) {
            System.out.print("array[" + i + "]: ");
            array[i] = sc.nextInt();
        }

        System.out.print("찾을 값은?: ");
        int key = sc.nextInt();

        int position = find(array, key, size);

        if (position == -1) {
            System.out.println("못 찾았습니다.");
        } else {
            System.out.println("array[" + position + "]에 존재");
        }
    }
}

 

 

 

 

해당 코드를 눈여겨볼 점

 

1. 배열 크기 입력받고 배열 생성 시 입력받은 값보다 +1 큰 배열로 생성한다. (보초를 넣기 위한 자리 마련)
2. 선형 검색 알고리즘 메서드 부분에서 배열의 맨 끝 자리는 값이 존재하지 않으니(기본값) 끝 자리에 key값을 넣는다.
3. i==size라는 것은 for문의 i가 보초까지 도달해서 key값을 찾은 것이다. 즉, 보초 이전에는 key값이 없으니 배열에 key값이 없다고 판단하면 된다.