[알고리즘] 순차 검색(Sequential Search)과 보초법(Sentinel Method)

순차 검색(Sequential Search)이란?

👉 원하는 키 값을 갖는 요소를 만날 때까지 맨 앞부터 순서대로 요소를 검색하는 알고리즘.
= 선형(linear)

종료 조건

1. 검색을 실패할 경우 : -1 반환
2. 검색을 성공할 경우 : 해당 요소의 인덱스 i 반환

예제

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;
    }
}

보초법(Sentinel Method)이란?

👉 반복의 종료를 알리는 특정한 값인 보초(Sentinel) 값을 사용하여 종료 조건 중 검색 실패 조건을 제거하여 판단 횟수를 줄이는 방법.

종료 조건

1. 검색을 성공할 경우(검색 대상 값을 만나거나, 보초값을 만남) : 해당 요소의 인덱스 i 반환

❗ 검색이 종료된 후 추가적으로 조건문을 통해 검색 대상 값이었는지 보초 값이었는지 판단을 해준다.

예제

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;
    }
}

Reference

• Do it 자료구조와 함께 배우는 알고리즘 입문 자바 편
• Tech-Stack(Github Pages)