[백준 1920] 수 찾기

https://www.acmicpc.net/problem/1920

1920번: 수 찾기

이진 탐색을 이용하여 수를 찾는 문제이다.

이진 탐색을 이용하기 위한 전제조건은 바로 오름차순으로 정렬이 되어 있어야 한다는 점이다.

오름차순으로 정렬하기 위한 정렬방법은 두가지 방법이 있다. 하나는 qsort, 또다른 하나는 bubble sort

 

bubble sort의 시간복잡도는 O(N^2)이기 때문에 qsort로 문제를 풀었다. 

<stdlib.h> 헤더파일안 qsort함수를 이용하여 코드를 짰다. 

qsort함수를 사용하기 위해 compare함수가 필요하다.

따라서 compare 함수를 구현해줬다. 

오름차순의 조건은 다음과 같다.

• a < b일 때는 -1을 반환
• a > b일 때는 1을 반환
• a == b일 때는 0을 반환

비교 함수를 정의할 때는 반드시 int형 반환값과 const void 포인터 매개변수가 두 개 있어야 한다. 그러나 const void 포인터로는 값을 비교할 수 없으므로 정렬할 배열의 자료형에 따라 const void 포인터를 변환한 뒤 역참조하여 값을 가져온다. 여기서는 정렬할 배열이 int형이므로 const void 포인터를 int 포인터로 변환한 뒤 역참조하여 값을 가져왔다.

 

compare함수를 위와 같이 안써도 된다. 

int compare(const void *a, const void *b)
{
    return *(int *)a - *(int *)b;    // 오름차순
}

위와 같이 작성해도 되는데 꼭 -1,0,1 값을 반환해야 하는 것은 아니다.

값이 같을 때만 0이면 되고, 값이 크거나 작을 때는 음수와 양수를 반환하면 된다.

 

 

 

참고문서

https://dojang.io/mod/page/view.php?id=638