Binary Search (2) - Iterative 방식으로 값 찾기

Binary Search (1) 에서 생성된 10,000개의 정수를 가지고 원하는 값을 찾아내는 함수를 구현하였다.

그리고 이 함수는 Iterative 방식, 즉 반복문을 통해 검색을 하는 방식으로 구현해 보았다.

int main(void) { int arr[arrSize]; int i=0, head=0; int searchNum; int searchCnt=0; int searchFlag = 0; printf("파일 LOAD --- OK.\n찾고자 하는 수를 입력하세요 : "); scanf("%d",&searchNum); tStart = GetMicroSecond(); // microsec 측정 시작 ///////////////////////////////////////////////////////////// // Binary Search 함수 call후 리턴값으로 카운트 값을 받아온다. searchFlag = BinarySearch_iter(arr, searchNum, head, arrSize-1, &searchCnt); // iterative 방식 ///////////////////////////////////////////////////////////// tStart = GetMicroSecond() - tStart; // microsec 측정 종료 if(searchFlag == 1) { printf("찾고자 하는 %d값을 %d번 비교해서 찾았습니다. (%d microsec)\n",searchNum, searchCnt, tStart); } else { printf("찾고자 하는 %d값을 %d번 비교했지만 없었습니다. (%d microsec)\n",searchNum, searchCnt, tStart); } return 0; }

searchFlag 라는 int형 변수에 함수를 달아 주었는데, 원하는 값을 찾았을 때에는 1을 return하고 값을 찾지 못했을 때에는 0을

return 하도록 함수를 만들어 주었다.

int BinarySearch_iter(int* _arr, int _searchNum, int _head, int _tail, int* _searchCnt) { int mid=0; while(_tail >= _head) { mid = (_head + _tail) / 2; (*_searchCnt)++; // 카운트를 1씩 증가시켜준다. if(_searchNum > _arr[mid]) // 찾고자 하는 값이 중간값보다 클때 { _head = mid + 1; // head값은 mid값 다음값부터 시작 } else if(_searchNum < _arr[mid]) // 찾고자 하는 값이 중간값보다 작을때 { _tail = mid - 1; // tail값은 mid값 하나 앞의 값으로 변경 } else if(_searchNum == _arr[mid]) // 값을 찾았을때 { //flag = 1; return 1; // 값이 찾아지면 1을 리턴한다 } } return 0; // while을 다 돌고 나와서도 값을 찾지 못한 경우에는 값이 없는 경우이므로 0을 리턴한다. }

함수 내에서 while문이 한번씩 돌 때 마다, 즉 비교를 한번씩 할 때마다 searchCnt를 1씩 증가시켜주고,

메인함수에서 넘겨받은 포인터 변수로 array의 head값과 tail값을 연산에 맞춰 변형 시켜가면서 연산을 해 주었다.

이렇게 구현한 함수를 이용하여 실제로 3930이라는 수를 검색해 보고 검색에 걸리는 시간을 측정해 보았다.

총 13번 비교과정을 통해 2 microsec가 소요되는 것을 확인할 수 있었다.

다음으로는 Recursive한 방법을 이용한 함수를 통해서 검색을 해보고 소요된 시간을 측정해 보도록 하겠다.