순차 탐색, 보초법

순차탐색

- 원하는 값을 찾기 위해서 배열의 첫번째 요소부터 마지막 요소까지 차례대로 모두 확인하는 방법

 

<코드>

import java.util.Scanner;

public class SearchExam {
    static int sequentialSearch(int[] arr, int key){
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == key)
                return i; // 키와 일치하는 요소의 인덱스 반환
        }
        return -1; // 검색 실패 시 -1 반환
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.print("찾고자하는 정수를 입력하세요: ");
        int key = sc.nextInt();
        int[] arr = {1,3,5,33,56,2,44};

        int index = sequentialSearch(arr, key);

        if (index != -1){
            System.out.println("당신이 찾는 데이터는 " +index+"번째 인덱스에 있습니다.");
        }else {
            System.out.println("당신이 찾는 데이터가 존재하지 않습니다.");
        }
    }
}

 

<설명>

찾고자 하는 값을 입력하면 sequentialSearch() 메소드에서 배열의 첫번째 요소부터 마지막 요소까지 순차적으로 확인을 한다.

도중에 원하는 값을 찾으면 값이 위치하는 요소의 인덱스를 반환한다.

 

순차탐색(보초법)

- 찾고자 하는 값(key)를 마지막 배열 요소에 추가 -> 배열의 크기를 벗어났는지 체크하지 않아도 됨

즉, for문을 사용하지 않고 while문을 사용하여 구현 가능

 

<코드>

import java.util.Scanner;

public class LinearSearchSentinel {
    // 배열 arr에서 key와 일치하는 요소를 보초법을 사용하여 선형 검색
    static int linearSearchSentinel(int[] arr, int size, int key) {
        int i = 0;
        arr[size] = key; // 보초 추가

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

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

        System.out.print("요소 개수: ");
        int num = stdIn.nextInt();
        int[] array = new int[num + 1]; // 요소 개수가 num + 1인 배열로, 마지막은 보초용

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

        System.out.print("찾을 값: "); // 찾고자 하는 값 입력
        int key = stdIn.nextInt();

        int index =linearSearchSentinel(array, num, key); // 배열 array에서 key를 검색

        if (index == -1)
            System.out.println("찾는 값의 요소가 없습니다.");
        else
            System.out.println("찾는 값은 array[" + index + "]에 있습니다.");
    }
}