[알고리즘-PS] Java에서 선형 검색 구현하는 방법.

검색하는 방법중 가장 기본적이며 자주 사용하는 알고리즘으로 알고리즘을 처음 학습한다면 필수로 알아야 한다.

선형 검색

알고리즘 정의

선형 검색이란 요소가 직선 모양으로 늘어선 배열에서 원하는 값을 찾기 위해 0번째 index에서 부터 배열의 끝까지 순차적으로 index를 비교하여 값을 찾는 알고리즘이다.

종료 조건

• 조건 1 : 검색할 값을 발견하지 못하고 배열의 끝을 지나간 경우
• 조건 2 : 검색할 값과 같은 요소를 발견한 경우

시간 복잡도

입력 배열의 길이가 n 인 경우 n/2

소스 코드

실행 결과

선형 검색의 보초법

선형 검색은 반복할 때 마다 종료 조건을 모두 검사한다. 하지만 이 비용을 절반으로 줄일 수 있는 방법이 바로 선형검색의 보초법이라고 한다.

 

보초법은 arr[0] ~ arr[5] 까지 있는 배열을 받아들이면 임의적으로 배열의 칸 수를 1칸 늘려 제일 마지막 인덱스에 검색을 원하는 key 값을 삽입하여 종료 조건 중 종료 조건 1 : 검색할 값을 발견하지 못하고 배열의 끝을 지나간 경우 의 조건 검사 비용을 줄이는 방법을 사용한다.

 

 

종료 조건을 다시 보자.

선형 검색의 종료 조건

• 조건 1 : 검색할 값을 발견하지 못하고 배열의 끝을 지나간 경우
• 조건 2 : 검색할 값과 같은 요소를 발견한 경우

여기서 조건 1을 없애고 조건 2로만 종료를 표시할 수 있게 한다.

선형 검색 보초법의 종료 조건

• 조건 1 : 검색할 값과 같은 요소를 발견한 경우

소스 코드

import java.util.Scanner;

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

        int num = input.nextInt(); // 요솟 수
        int[] x = new int[num+1];

        for (int i = 0; i < num; i++) {
            x[i] = input.nextInt();
        }

        int key = input.nextInt();

        int ans = Sentry.sentry(x, num, key);
        if(ans == -1) System.out.println("요소가 존재하지 않습니다.");
        else System.out.println(key+"는" + "arr[" + ans +"] 에 있습니다.");
    }
}

class Sentry {
    static int sentry(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;
    }
}