이진 탐색이란?
이진 탐색이란 오름차순으로 정렬된 리스트에서 특정한 값의 위치를 찾는 알고리즘입니다. 처음과 중간의 값을 임의의 값으로 선택하여, 그 값과 찾고자 하는 값의 크고 작음을 비교하는 방식을 채택합니다.
이진 탐색 예시
이진 탐색을 위한 헤더 파일을 만듭니다.
binarySearch 함수 파일을 만듭니다.
마지막으로 메인 함수 파일을 만듭니다.
오름차순으로 정렬된 배열이 있습니다.
{ 1, 2, 4, 7, 8 }
그리고 rand()%10 + 1;을 통해 난수를 받습니다.
이 배열에서 이진 탐색을 이용하여 rand()%10 + 1;의 값을 찾아봅니다.
- 첫 번째 시도
난수로 생성된 값이 7이라고 가정합니다. 우선 가운데에 위치한 임의의 값 4를 선택합니다. 선택한 값 4와 찾고자 하는 값 7을 비교합니다.
4 < 7이므로 7은 4의 좌측에 존재한다는 것을 알 수 있습니다.
- 두 번째 시도
4를 기준으로 좌측에 있는 배열 값들을 대상으로 다시 탐색을 진행합니다.
{ 7, 8 }
이번에는 7이 8보다 작고 배열에 값이 하나만 남게 되므로 값을 확인해보면, 7 == 7로 원하는 값을 찾습니다.
- 종료 조건
탐색하고자 하는 배열이 더 이상 존재하지 않으면 찾고자 하는 값이 배열에 존재하지 않는다는 것으로 판단하여 탐색을 종료합니다.
이진 탐색 예시 결과
먼저, Makefile을 통해 정적 라이브러리를 생성하고 컴파일 합니다.
아래는 make 명령어를 통한 예시 결과입니다.
