선형 검색과 보초법

🔎검색 알고리즘은 무엇인가?

검색 알고리즘의 의미는 데이터베이스 내 수집 된 여러 아이템 중에서 특정 성질 혹은 키 값을 구성한 데이터를 찾아내는 알고리즘입니다. 이러한 알고리즘을 사용할 때 주의할 점은

• 상대적인 알고리즘의 수행 시간
• 활용 용도나 목적, 자료구조 등 체계적인 부분
• 데이터의 추가, 수정, 삭제 등 작업에 소요되는 비용

만약 어떤 목적을 이루기 위해 선택할 수 있는 알고리즘의 개수가 여러 가지인 경우 용도나 목적, 실행 속도, 자료구조 등을 잘 고려하여 작업에 소요되는 비용을 종합적으로 평가하여 효율적인 알고리즘을 선택하여 그 상황의 문제에 적용을 잘해야 합니다.

📈선형 검색에 대해 알아보자

선형 검색은 검색 알고리즘에서의 가장 기본이 된다고 말할 수 있는 검색 알고리즘 입니다. 요소가 직선 모양으로 늘어선 배열에서 원하는 키 값을 갖는 요소를 만날 때까지 맨 앞에서 순서대로 요소를 검색합니다. 선형 검색 또는 순차 검색이라고 부르기도 합니다. 

int 정수열 배열에서 선형 검색 알고리즘을 활용하여 숫자 2를 검색하는 과정 - 검색 성공

위의 사진은 선형 검색 알고리즘을 활용하여 배열 속에서 숫자 '2'를 찾는 과정입니다. 순차적으로 0번째 인덱스부터 높은 인덱스 값으로 이동하면서 '2'를 찾고 있습니다. 위의 사진은 배열에 찾는 값인 '2'가 존재하므로 선형 검색 성공입니다. 하지만 배열 속에서 찾는 값이 존재하지 않으면 어떻게 될까요? 이번에는 위의 배열에서 숫자 '5'를 찾아보도록 하겠습니다.

int 정수형 배열에서 선형 검색 알고리즘을 활용하여 숫자 5를 검색하는 과정 - 검색 실패

예상한 결과와 같이 위의 배열에는 찾고자 하는 값인 5가 존재하지 않기 때문에 배열 인덱스의 값을 모두 찾아보아도 그 값이 존재하지 않는다는 것을 알 수 있습니다. 즉 한 칸씩 옮기면서 구성하던 인덱스의 값이 배열의 크기와 값이 같게 되었으며 검색 실패입니다.

🎉 선형 검색의 종료 조건은?

선형 검색의 종료 조건

1. 검색할 값과 같은 요소를 발견한 경우(검색 성공)

2. 검색할 값을 발견하지 못하고 배열의 끝을 지나간 경우(검색 실패)

 선형 검색의 종료 조건 1과 2를 판단하는 선형 검색의 검색 판단 횟수는 배열의 요솟수가 n개일 때 평균 n/2회입니다.

💻 선형 검색을 구현해보자!

public class SeqSearch {
    public static Scanner scanner = new Scanner(System.in);
    public static void main(String[] args) {
        System.out.print("요솟수를 입력해주세요 : "); int input = scanner.nextInt();
        int[] arr = new int[input];
        setArr(arr);

        System.out.print("배열에서 검색할 값을 입력해주세요 : "); int searchInput = scanner.nextInt();
        int index = findArr(arr, searchInput);

        if(index == -1) System.out.println("찾으시는 값은 배열에 존재하지 않습니다.");
        else System.out.println("찾으시는 값은 배열 x[" + index + "]에 존재합니다.");
    }
    public static void setArr(int[] arr){
        for(int i = 0; i < arr.length; i++){
            System.out.print("배열의 x[" + i + "]의 값을 입력해주세요 : ");
            arr[i] = scanner.nextInt();
        }
    }
    public static int findArr(int[] arr, int searchInput){
        for(int i = 0; i < arr.length; i++) if(arr[i] == searchInput) return i;
        return -1;
    }
}

먼저, 사용자에게 배열의 요소수 즉 크기를 입력받고 그 크기에 맞게 int 정수형 배열을 생성하였습니다. 그 후 배열의 요소를 각각 입력을 하여 배열에 저장을 하였습니다. 배열에 요소를 모두 입력을 받았다면 최종적으로 사용자에게 배열에서 검색할 값을 입력받습니다. 그러면 프로그램 내에서는 선형 검색 알고리즘을 통해 배열의 인덱스 0번째부터 그 값을 순차적으로 검색하기 시작합니다.

 

만약 사용자가 입력한 값이 배열에 존재한다면 그 값의 인덱스 값을 반환하고 만약 배열의 처음부터 끝까지 모두 검색을 수행하였으나 값이 존재하지 않는다면 findArr 매서드의 for문을 탈출하여 최종적으로 숫자 -1을 반환하여 검색 실패를 의미하고 있습니다.

🎯 보초 법이 대체 뭐야?

보초 법은 선형 검색 알고리즘을 활용할 때 함께 사용을 한다면 효율성이 있는 기술?, 방법?이라고 할 수 있다. 위에서 선형 검색 알고리즘의 종료 조건은 총 2가지였다. 어떻게 보면 적다고 할 수 있지만 종료 조건을 검사하는 비용은 결코 무시할 수 없다. 그래서 그 종료 조건을 검사하는 비용을 줄여주기 위한 방법으로 보초 법을 활용하면 된다. 아래의 그림을 통해 보초법을 설명하겠습니다.

기존의 배열에 보초 값이 추가 되어있는 모습입니다. (기존의 데이터 검색 성공)

기존의 배열에 보초 값이 추가 되어있는 모습입니다. (기존의 데이터 검색 성공)

 

기존의 배열에 보초 값이 추가되어 있는 모습입니다. (보초 데이터 검색 성공)

 

 

보초 법을 사용하는 간단한 방법을 알려드리도록 하겠습니다. 기존의 배열에서 요솟수를 1을 추가하여 배열 마지막 인덱스에 사용자가 찾는 값을 저장해둡니다. 그러면 선형 검색을 통해 순차적으로 값을 찾게 될 것이며 검색 조건 2번 배열에서 값을 발견하지 못하고 배열의 끝을 지나간 경우는 이제 존재하지 않게 될 것입니다. 즉 검색 실패의 경우는 앞으로 존재할 수가 없는 것을 알 수 있습니다.

 

최종적으로 저희는 이제 선형 검색을 통해 찾은 값이 기존의 배열에 존재하는 데이터인지 또는 보초로 설정해둔 특정의 값인지 구별만 할 수 있도록 코드를 작성한다면 선형 검색 알고리즘의 종료 조건을 검사하는 비용을 50%나 줄일 수 있어 더욱 효율적입니다.

📆 보초법을 사용해보자!

아래의 코드는 위에서 예기한 것과 같이 사용자로부터 배열의 크기를 입력받은 것에서 1 크게 배열을 구성합니다. 그 후 배열 마지막 인덱스에 사용자가 찾는 값을 추가합니다. 그렇다면 검색 실패는 절대 발생하지 않고 매번 검색 성공을 합니다. 그러면 이제 그 검색 성공의 값이 기존의 배열에 데이터 값인지 또는 보초의 값인지 판단을 해야 합니다. 판단의 기준은 인덱스 값으로 판단할 수 있습니다.

 

만약 그 인덱스의 값이 배열의 마지막 인덱스라면 찾은 값은 보초의 값이며 -1을 반환합니다. 그러나 그렇지 않다면 기존의 배열에 데이터 값이므로 그 값의 인덱스를 전달합니다. 전달받은 값을 통해 저희는 찾은 값의 검색 성공, 실패 여부를 확인할 수 있습니다.

public class SeqSearchSen {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        System.out.print("요솟수를 입력해주세요 : "); int num = scanner.nextInt();
        int arr[] = new int[num + 1];

        for(int i = 0; i < num; i++){
            System.out.println("배열 x[" + i + "] : ");
            arr[i] = scanner.nextInt();
        }

        System.out.println("검색할 값을 입력해주세요 : "); int ky = scanner.nextInt();
        int idx = seqSearchSen(arr, num, ky);

        if(idx == -1) System.out.println("배열에서 검색하신 값은 존재하지 않습니다.");
        else System.out.println(ky + "은(는) 배열 x[" + idx + "]에 존재합니다.");
    }

    public static int seqSearchSen(int arr[], int num, int key){
        int i = 0;
        arr[num] = key;

        while(true){
            if(arr[i] == key) break;
            i++;
        }
        return i == num ? -1 : i;
    }
}