[자료구조와 알고리즘] 선형 검색과 보초법

선형 검색(Linear Search) 은 배열이나 리스트에서 원하는 값을 찾을 때, 처음부터 하나씩 차례대로 비교하면서 탐색하는 알고리즘입니다.

• 배열의 첫 번째 요소부터 마지막 요소까지 차례로 비교하며 찾고자 하는 값과 일치하는지 검사합니다.
• 일치하는 값을 찾으면 해당 인덱스를 반환하고, 찾지 못하면 -1을 반환합니다.
• 정렬되지 않은 배열에서도 사용할 수 있지만, 평균적으로 시간 복잡도가 O(n)으로 비효율적입니다.

public class LinearSearch {
    // 선형 검색 메서드
    public static int linearSearch(int[] arr, int target) {
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == target) {
                return i; // 찾으면 해당 인덱스 반환
            }
        }
        return -1; // 찾지 못하면 -1 반환
    }

    public static void main(String[] args) {
        int[] arr = {3, 8, 2, 7, 5, 6};
        int target = 7;

        int index = linearSearch(arr, target);

        if (index != -1) {
            System.out.println("값 " + target + "은(는) 인덱스 " + index + "에 있습니다.");
        } else {
            System.out.println("값 " + target + "을(를) 찾을 수 없습니다.");
        }
    }
}

 

보초법(Sentinel Linear Search)은 선형 검색을 최적화한 방식으로, 반복문에서 불필요한 조건 검사 횟수를 줄이는 방법입니다.

보초법의 원리

• 배열의 마지막 위치에 찾고자 하는 값을 임시로 저장(보초, Sentinel) 합니다.
• 보초를 둠으로써 배열을 끝까지 검색해야 하는 경우에도 반복문에서 조건을 체크하는 횟수를 줄일 수 있습니다.
• 보초 덕분에 반복문 안에서 i < arr.length 같은 범위 조건을 체크하지 않아도 되는 장점이 있습니다.

public class SentinelLinearSearch {
    // 보초법을 이용한 선형 검색
    public static int sentinelLinearSearch(int[] arr, int target) {
        int n = arr.length;
        int last = arr[n - 1]; // 배열의 마지막 요소 저장
        arr[n - 1] = target;   // 보초(Sentinel) 설정

        int i = 0;
        while (arr[i] != target) { // 보초 덕분에 i < n 조건 체크 필요 없음
            i++;
        }

        arr[n - 1] = last; // 배열 원상 복구

        if (i < n - 1 || arr[n - 1] == target) { // 원래 값이 마지막 위치에 있었던 경우 고려
            return i;
        }
        return -1;
    }

    public static void main(String[] args) {
        int[] arr = {3, 8, 2, 7, 5, 6, 0}; // 마지막 요소는 보초를 위해 여유 공간을 둠
        int target = 7;

        int index = sentinelLinearSearch(arr, target);

        if (index != -1) {
            System.out.println("값 " + target + "은(는) 인덱스 " + index + "에 있습니다.");
        } else {
            System.out.println("값 " + target + "을(를) 찾을 수 없습니다.");
        }
    }
}

보초법의 장점

1. 배열 끝을 체크하는 조건을 생략할 수 있음 → 실행 속도가 빨라짐
2. 반복문 내 조건 검사가 줄어들어 코드가 단순해짐
3. 최악의 경우에도 일반 선형 검색과 동일한 O(n)의 시간 복잡도를 가짐

결론

• 선형 검색은 간단하고 정렬되지 않은 데이터에서도 사용할 수 있지만, 검색 속도가 느릴 수 있음.
• 보초법을 사용하면 검색 속도를 조금 더 최적화할 수 있음.
• 하지만 데이터가 많거나 정렬된 경우, 이진 검색(Binary Search)과 같은 효율적인 알고리즘을 사용하는 것이 좋음.