[Algorithm] 선형검색(Linear search) / 보초법(Sentinel method)

 

선형 검색 (Linear search)

■ 정의

 - 요소가 직선 모양으로 늘어선 배열에서 검색은 원하는 키 값을 갖는 요소를 만날 때까지 맨 앞부터 순서대로 요소를 검색하는 기법

 

■ 사용 예

 - 찾으려는 값이 2일 경우

 - 찾으려는 값이 7일 경우

 - 찾는 값이 3으로 존재하는 경우 앞에서부터 순차적으로 검색 후 index 값이 3에서 탐색을 종료 함

 - 찾는 값이 7로 존재하지 않는 경우 마지막까지 검색 후 -1을 return 후 종료 함

 

■ Code

 - while문으로 작성한 선형검색

public class SeqSearch {
    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++;
        }
    }

 

- for문으로 작성한 선형검색

public class SeqSearchFor {
    static int seqSearch(int[] a, int n, int key) {
        for (int i = 0; i < n; i++) {
            if (a[i] == key)
                return i;
        }
        return -1;
    }

---

보초법 (Sentinel method)

■ 정의

 - 배열의 index + 1에 검색하려는 값을 저장하여(보초) 선형검색을 하는 기법
 - 이는 비용을 반(50%)으로 줄일 수 있음

 

■ 사용 예

 - 찾으려는 값이 7일 경우

- 선형검색과는 다르게 임의로 index + 1 위치에 찾으려는 value값을 만들고 검색을 함

 - index + 1의 위치를 '보초' 라고 함

 

■ Code

 - while문으로 작성한 보초법

public class SeqSearchSen {
    static int seqSearchSen(int[] a, int n, int key){
        int i = 0;
        a[n] = key;

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

 

 - for문으로 작성한 보초법

public class SeqSearchSenFor {
    static int seqSearchSen(int[] a, int n, int key) {
        int i;
        a[n] = key;

        for (i = 0; a[i] != key; i++)
            ;
        return i == n ? -1 : i;
    }