배열을 검색(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. 이진검색
