3-2. 선형 검색(Linear Search)

<선형 검색>

: 배열에서 검색하는 방법 가운데 가장 기본적인 알고리즘. 배열에서 순서대로 검색하는 유일한 방법이기도 하다.

요소가 직선 모양으로 늘어선 배열에서의 검색은 원하는 키 값을 갖는 요소를 만날 때까지 맨 앞부터 순서대로 요소를 검색하면 되는데, 이것이 선형 검색(linear search) 또는 순차 검색(sequential search)라는 알고리즘이다.

 

 

 

・검색의 종료 조건

① 검색할 값을 발견하지 못하고 배열의 끝을 지나간 경우(검색 실패)

② 검색할 값과 같은 요소를 발견한 경우(검색 성공)

 

 

 

-while문 사용

 

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문 사용

 

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

 

 

 

 

 

<보초법(sentinel method)>

: 선형 검색의 두 가지 종료 조건을 검사하는 비용을 반(50%)으로 줄이는 방법

배열의 맨 마지막에 키값을 저장해(보초) if문을 반으로 줄인다.

 

 

 

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;
    }