검색 알고리즘 - 선형 검색

검색 알고리즘

데이터 집합에서 원하는 값을 가진 요소를 찾아내는 알고리즘

 

배열 검색

• 선형 검색 : 무작위로 늘어놓은 데이터 모임에서 검색을 수행
• 이진 검색 : 일정한 규칙으로 늘어놓은 데이터 모임에서 검색을 수행
• 해시법 : 추가, 삭제가 자주 일어나는 데이터 모임에서 검색을 수행

 

선형 검색[linear search]

원하는 키 값을 갖는 요소를 만날 때까지 맨 앞부터 순서대로 요소를 검색하게 되는데, 이를 선형 검색 또는 순차 검색 알고리즘이라고 한다.

[검색의 종료 조건]
1) 검색할 값을 발견하지 못하고 배열/리스트의 끝을 지나간 경우 - 검색 실패
2) 검색할 값과 같은 요소를 발견한 경우 - 검색 성공

 

■ 선형 검색 알고리즘

배열 a의 처음부터 끝까지 n개의 요소를 대상으로 값이 key인 요소를 선형 검색하고 검색한 요소의 인덱스를 반환

key인 요소가 존재하지 않을 경우 -1를 반환

public class SeqSearch {

    public static int seqSearch(int[] a, int n, int key){
        int i = 0;
        while (true){
            if(i == n)
                return -1;  //검색 실패
            if(a[i] == key)
                return i;
            i++;
        }
    }

    public static int seqSearch(int[] a, int key){
        //for문을 통한 배열 탐색
        for(int i=0; i<a.length; i++){
            if(a[i] == key)
                return i;
        }
        return -1;
    }

    public static void main(String[] args) {
        int[] a = new int[]{22, 8, 55, 32, 120, 50,70};
        int key = 55;

        int idx = seqSearch(a, a.length, key);
        int idx2 = seqSearch(a, key);

        if(idx == -1){
            System.out.println("그 값은 요소에 없습니다.");
        }else{
            System.out.println(key + "는/은 " + idx  + "에 있습니다.");
            System.out.println(key + "는/은 " + idx2  + "에 있습니다.");
        }
    }
}

■ 보초법

검색 알고리즘의 종료 조건을 반으로 줄일 수 있는 방법으로 보초법을 활용한다.검색하기 전에 검색하고자 하는 키 값을 맨 끝 요소에 저장을 하게 되면 위의 종료 조건 1을 수행하지 않아도 되므로 검사 비용을 절감할 수 있다.

public static int seqSearchSen(int[] a, int n, int key) {
        int[] x = new int[n + 1];
        for (int i=0; i<x.length; i++) {
            x[i] = a[i];
        }
        x[n+1] = key;   //보초를 추가

        int j = 0;
        while (true) {
            if (x[j] == key)
                break;
        }
        j++;
        return j == n+1 ? -1 : j;
}