C 언어 표준 라이브러리에는 잘 알다시피 배열 데이터에 대해서 간단한 검색과 정렬 알고리즘을 구현해 놓은 함수가 존재한다.
정렬을 수행하는 qsort()가 대표적인 예이고, 이미 정렬된 배열에 대해서 이분 검색을 수행하는 bsearch()도 유용하다.
이들 검색과 정렬 함수는 비슷한 형태의 인자를 받아서 동작한다. 배열을 가리키는 포인터, 각 원소의 개수와 크기, 그리고 찾고자 하는 원소의 값, 그리고 비교 함수의 포인터이다. 비교 함수는 두 원소의 비교를 수행하여 대소 관계를 리턴값의 부호 또는 0 여부로 알려 주어야 한다. 이렇게 함으로써 int든 float든 그 어느 자료형이라도 범용적으로 검색하거나 정렬을 수행할 수 있다.
그런데 C 언어는 이분 검색뿐만 아니라 선형 검색을 하는 함수도 제공한다. 찾는 원소와 같은 값이 나올 때까지 배열을 처음부터 끝까지 단순히 뒤지기만 하는 알고리즘 말이다. 동작 방식은 단순하기 그지없지만, 이분 검색과 더불어 그냥 일관성을 위해서 선형 검색도 함수로 표준화한 듯하다. 선형 검색이 받아들이는 비교 함수는 두 값의 대소 비교를 할 필요가 없이 두 값이 단순히 같으면 0, 그렇지 않으면 nonzero만 되돌려도 된다.
그런데 본인은 C 언어가 제공하는 선형 검색 함수의 형태를 보고는 놀라지 않을 수 없었다.
1. 이분 검색이 bsearch이니 선형 검색은 응당 lsearch일 거라고 본인은 생각했다. 그런데 선형 검색 함수는 _lsearch와 _lfind로 나뉘어 있고, 어찌 된 이유인지 함수 이름 앞에 밑줄이 추가돼 있다. 이분 검색과 정렬 함수는 stdlib.h에도 선언이 되어 있는 반면, 선형 검색 함수는 거기에 없으며 반드시 생소한 search.h를 인클루드 해 줘야 한다. 왜 이런 차이가 존재하는지부터 의문이다.
2. _lsearch는 원소를 찾아서 이게 배열에 존재하지 않으면, 그 원소를 배열의 끝에다가 추가를 한다. 따라서 이 함수는 매개변수만 올바르다면, 원하는 원소가 배열에 없다고 하더라도 NULL을 리턴하지 않는다. 그 반면 _lfind는 read-only 함수로, 원하는 원소가 없으면 NULL을 되돌린다. 그러므로 정확하게 bsearch 함수의 동작 방식만 선형 검색의 형태로 원한다면 _lsearch가 아닌 _lfind를 써야 한다.
3. bsearch와는 달리, 선형 검색 함수는 배열 원소의 개수를 넘겨주는 인자가 포인터형이다. 그것도 size_t도 아닌 unsigned int의 포인터이기 때문에 64비트 환경에서도 여전히 32비트 값 전달만 가능하다는 한계마저 그대로 지닌다. ㅜ.ㅜ 왜냐하면 _lsearch의 경우, 원하는 원소가 배열에 존재하지 않아서 그 원소가 배열 뒤에 추가되었을 경우, 배열 원소 개수를 1 증가시켜 주기 위해서이다.
그러나 배열 원소 추가를 하지 않는 _lfind라면 배열 원소 개수 인자가 포인터여야 할 필요가 전혀 없고 bsearch처럼 size_t 값을 그대로 받기만 하면 된다. 왜 _lfind까지 _lsearch처럼 그렇게 포인터를 받게 해 놓았는지 모르겠다.
Posted by 사무엘
