DS, ALGORITHM: 기본 자료구조(검색)

배열을 검색(Searching)하는 방법에 대해 알아보고자 한다. 쌓인 데이터들 중 내가 원하는 데이터를 찾을 때 쓰는 방법으로 효율성이 중요한 부분이다. 검색할 때 중요한 것은 '~~~한' 항목을 찾고자 하는지이다. 그 항목은 Key라고 부른다. 

1. 선형검색(Linear Search)

말 그대로 linear하게, 맨 앞에서 부터 순서대로 검색하는 것. 종료 조건은 두 가지가 있을 수 있다. 성공(key값과 같은 요소를 발견) 혹은 실패(key값을 발견하지 못하고 배열이 끝).

// while문 사용
int linear_search(const int array[], int array_size, int key){
	int i = 0; // 배열 인덱스
    while(1){
    	if( i == array_size ) // 실패
        	return -1;
        if( array[i] == key ) // 성공
        	return i;
        i++;
    }
}

// for문 사용
int linear_search(const int array[], int array_size, int key){
	int i; // 배열 인덱스
    for( i = 0 ; i < array_size ; i++ ){
    	if ( array[i] == key ) // 성공
        	return i; 
    }
    return -1; // 실패
}

 

• 보초법(sentinel method)

선형 검색은 종료 조건으로 성공, 실패 두 가지를 매번 검사하기 때문에, 비용이 크다. 효율적이지 않다는 의미. 따라서 그 비용을 반으로 절감하는 방법이 고안되었는데 그 것이 바로 보초법이다. 선형 검색의 두 가지 종료조건인 성공, 실패 중 실패를 검사하지 않도록 하는 것이다. 

 

---

2. 이진검색