[알고리즘] 선형 탐색 (배열 검색 알고리즘)

선형 탐색 (Linear Search)

원하는 키 값을 갖는 요소를 만날 때 까지 맨 앞부터 순서대로 요소를 검색하는 알고리즘

'선형 탐색' 또는 '순차 탐색' 이라고 한다.

 

선형 검색에서 배열 검색의 종료하는 조건은 2개!

아래의 조건 중 하나라도 성립을 하면, 검색을 종료한다.

 

조건 1. 종료 검색할 값을 발견하지 못하고 배열 끝을 지나간 경우 => 검색 실패 

조건 2. 종료 검색할 값과 같은 요소 발견한 경우 => 검색 성공

 

배열의 요소수가 n개일 때, 종료 조건 1&2를 판단하는 횟수는

평균 n/2회이다.

* 원하는 값이 배열에 존재하지 않는 경우? 1번은 n+1회, 2번은 n회 판단!

 

---

 

선형 탐색 사용 예시

import java.util.Scanner;

public class 선형탐색 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }

        System.out.print("검색할 값 : ");
        int search = sc.nextInt();
        int result = searchElement(arr, n, search);

        if (result == -1)
            System.out.println("요소 없음");
        else
            System.out.println("그 값은 " + result + "에 있음");
    }

    static int searchElement(int[] arr, int n, int search) {
        for(int i=0; i<arr.length; i++) {
            if(arr[i] == search) {
                return arr[i];
            }
        }
        return -1;
    }
}

선형 탐색을 이용해 

내가 검색한 값이 배열에 있는 지 없는 지 검색하는 코드이다.

arr 배열을 돌며, search(찾으려는 값)이 있으면 그 값을 return 하고, 

없는 경우엔 -1을 return 한다.

 

---

 

선형 검색은 반복할 때 마다 위에서 언급한 종료조건 1과 2를 모두 판단한다.

이 비용을 반(50%)로 줄이는 방법이 "보초법" 이다.

 

기존 코드는 종료 조건 1,2를 모두 판단해야 하지만, 보초법은 그를 반으로 줄일 수 있다.

배열의 끝에 보초값을 추가한다 (이를 위해 배열의 크기를 기존보다 +1로 설정해 생성해야 한다.)

while문을 돌며 search값을 배열에서 검색하는데,

 

이렇게 되면 키 값을 찾지 못하는 경우는 없다.

즉, 종료 조건 1이 없어도 되므로 보초는 반복문에서 종료 판단 횟수를 2회에서 1회로 줄이는 역할을 한다.

 

위의 코드를 보초법으로 바꿔 작성해봤다.

import java.util.Scanner;

public class 선형탐색_보초법 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        int[] arr = new int[n+1];
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }

        System.out.print("검색할 값 : ");
        int search = sc.nextInt();
        int result = searchElement(arr, n, search);

        if (result == -1)
            System.out.println("요소 없음");
        else
            System.out.println("그 값은 " + result + "에 있음");
    }

    static int searchElement(int[] arr, int n, int search) {
        int i = 0;
        arr[n] = search;

        while (true) {
            if (arr[i] == search)
                break;
            i++;
        }
        return i == n? -1 : i; // 보초값을 찾은거면 -1, 아니면 i반환
    }
}

이렇게 보초법을 적용해 if문의 판단 횟수를 줄일 수 있다.