[자료구조와 함께 배우는 알고리즘 입문] 3. 검색 알고리즘(1)

1. 검색 알고리즘이란?

1-1. 검색과 키 살펴보기 - 키값을 지정하는 방법

1. 키값과 일치하도록 지정
2. 키값의 구간을 지정
3. 키값과 비슷하도록 지정
4. 조건은 N개 이상으로 지정 가능

 

1-2 배열에서 검색하기

 

배열 내에서 찾고자 하는 데이터를 검색한다.

관련 알고리즘은 아래와 같다.

1. 선형 검색 : 무작위로 늘어있는 배열에서 검색
2. 이진 검색 : 일정한 규칙으로 늘어있는 배열에서 빠르게 검색 수행
3. 해시법 : 추가, 삭제가 자주 일어나는 배열에서 빠르게 검색/ 수행

 

2. 선형 검색

2-1. 선형 검색 알아보기

 

위에서 말한 것 처럼 선형검색은 무작위로 늘어있는 배열에서 찾고자 하는 데이터를 검색하는 것이다.

좀 더 이해하기 쉽게 표현하면 아래와 같다.

 

요걸 코드로 표현하면 아래와 같이 표현할 수 있다.

 static int seqSearch(int[]arr, int x, int key){
        int i=0;
        while(true){
            if(arr[i]==key){
                return i;
            }
            if(i==x){
                return -1;
            }
            i++;
        }
    }

이 메소드에서 받는 값은 배열 arr, 배열의 크기x, 찾고자 하는 데이터 값 key이다.

while문 안에서 key값과 배열 값을 비교해서 key값과 일치하면 해당 데이터의 인덱스 값을 반환해주고, 만약 일치하는 값이 없고 i가 배열의 크기인 x와 같다면 -1을 반환하게 된다.

 

이 while문을 for문으로 바꾼다면 다음과 같다.

 static int seqSearch(int[]arr, int x, int key){

        for (int i = 0; i < arr.length; i++) {
            if(arr[i]==key){
                return i;
            }
        }
        return -1;

    }

for문 내에서 인덱스 i에 해당하는 데이터가 key값과 같으면 해당 인덱스 값을 반환해준다.

for문을 다 돌았는데도 key값과 일치하는 데이터를 찾지 못했다면 -1을 반환하게 된다.

 

선형 검색은 검색 값을 발견하지 못하고 배열의 끝을 지나갔거나 검색할 값과 같은 데이터를 발견했을 때 종료되기 때문에 종료 조건 검사비용이 꽤 크다.

 

 

2-2. 보초법으로 선형검색 구현하기

 

앞서 말한 기본 선형검색의 큰 검사 비용을 반으로 절감하는 방법이 보초법이다.

배열의 맨 마지막에 보초로 찾고자 하는 값을 저장해두고 검색을 진행하는 방법이다.

따라서 위의 코드의 x값을 원래 만들고자 한 배열의 크기보다 하나 더 크게 설정해준다.

(배열의 길이 설정 시 x -> x+1값으로 설정)

 

이를 구현한 코드는 아래와 같다.

 static int seqSearchSen(int[] arr, int x, int key){
        int i=0;
        arr[x] = key;
        
        while(true){
            if(arr[i]==key){
                break;
            }
            i++;
        }
        return i==x? -1 : i;
    }

먼저 배열의 맨 끝에 key값을 하나 추가해준다.

while문 내에서 배열의 값 중 key값과 일치하는 부분이 있으면 break로 while문을 종료시킨다. 만약 일치하지 않는다면 i를 증가시키고, i를 맨 마지막 인덱스 값, 즉 x가 되도록 한다.

i가 x와 같다면 -1을 return시키고, 아니라면 i값을 return시켜서 key값에 일치하는 데이터의 인덱스값을 반환한다.

보초법을 통해서 "색할 값과 같은 데이터를 발견했을 때 종료"의 종료 조건만 주어 검사 비용을 줄일 수 있다.