01. 선형 검색 (Linear Search)

2019. 8. 21. 17:46CSE/Data Structure

* 정의 
: 요소가 직선 모양으로 늘어선 배열에서의 검색

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

 

* 예외 처리

- 배열 내에 원하는 키 값이 없을 경우

   => 보초법(sentinel mothod) : 원래 데이터의 맨 끝에 검색할 값을 추가한 후(보초를 추가함) 검색

 

* java로 구현한 코드

- example_1 (보초법 X)

public class example_1 {
    
    static int linearSearch(int[] a, int n, int key){
        //요솟수가 n인 배열 a에서 key를 선형 검색 하는 메소드
        int result = -1;
        for(int i = 0; i<n; i++){
            if(a[i]==key){
               result = i;
                break;
            }
        }
        return result;
    }
}

- example_2 (보초법 O)

 

public class example_2 {

    static int linearSearch(int[] a, int n, int key){
        //요솟수가 (n+1)인 배열 a에서 key를 선형 검색 하는 메소드 + 보초법
        int result = -1;
        
        a[n] = key; // 보초 추가

        for(int i = 0; i<n; i++){
            if(a[i]==key){
                result = i;
                break;
            }
        }

        if(result == n){
            return -1;
        } else {
            return result;
        }
    }
}

'CSE > Data Structure' 카테고리의 다른 글

Hash Table, ArrayList  (0) 2021.07.19
04. Queue  (0) 2020.02.02
03. Stack  (0) 2020.01.21
02. 이진 검색(Binary Search)  (0) 2019.08.21