BINARY SEARCH (이진탐색)
What is it?
- Binary search(이진탐색). 많은 탐색기법 중 간단하고 속도가 빨라 자주 쓰이는 로직이다.
- 배열을 계속 반으로 갈라 UP/DOWN을 하면서 (1/2)n개로 줄여가며 탐색한다.
- 반드시 정렬된 배열에서만 사용할 수 있다.
- Worst Case, 'O( logn )'
- 너무 간단한 코드라 자세한 설명은 생략한다.
CODE
/************************************************ * BINARY SEARCH ****************************** * ********************************* binaryS.c **** * ***********************************************/ #include <stdio.h> /* Length of Array */ #define MAX_BUFF 5 /* Data which into Array */ typedef struct DATA { int mKey; // 키 int mValue; // 값 } DATA; /****************************** * * BINARY SEARCH by Recursive * * ***************************** */ int BinarySearch(struct DATA aSortedArray[], int aBegin, int aEnd, int aFind) { /* Arguments */ // aSortedArray[] : 정렬된 배열 // aBegin : 배열의 0번째 인덱스 // aEnd : 배열의 끝 인덱스 // aFind : 찾고자 하는 값 X /* Array's middle index */ int mMid = 0; /* Escape condition */ if ( aBegin > aEnd ) { return -1; } /* Declare mMid's value */ mMid = ( aBegin + aEnd ) / 2; /* If i find the value X, */ if ( aSortedArray[mMid].mValue == aFind ) { /* Return */ return mMid; } /* If arry[mid] > X */ else if ( aSortedArray[mMid].mValue > aFind ) { /* Recursive, aEnd is mMid-1 */ return BinarySearch( aSortedArray, aBegin, mMid-1, aFind ); } /* If arry[mid] < X */ else if ( aSortedArray[mMid].mValue < aFind ) { /* Recursive, aBegin is mMid+1 */ return BinarySearch( aSortedArray, mMid+1, aEnd, aFind ); } } /* MAIN FUNCTION */ int main() { /* declare an Array which has struct datas */ struct DATA arr[MAX_BUFF]; /* Variables */ int mFindValue = 0; // 입력받는 찾을 값 int mIndex = 0; // 찾은 값의 인덱스 int inputKey = 0; // 배열에 들어갈 입력받은 key값 int inputValue = 0; // 배열에 들어갈 입력받은 value값 printf("\nEnter the 5 KEYs and VALUEs which you want : \n"); printf("\n\n :::: WARNING : YOU MUST ENTER BY ORDER FOR VALUEs::::\n\n"); for(int i = 0; i < MAX_BUFF; i++) { /* Fill the Array with inputed values */ scanf("%d", &inputKey); scanf("%d", &inputValue); arr[i].mKey = inputKey; arr[i].mValue = inputValue; printf("KEY : %d VALUE : %d and\n", inputKey, inputValue); } printf("\n\nThen, current array's status is : \n\n"); printf("Keys : [ "); for(int i = 0; i < MAX_BUFF; i++) { printf("%d ", arr[i].mKey); } printf("]\n"); printf("VALUEs : [ "); for(int i = 0; i < MAX_BUFF; i++) { printf("%d ", arr[i].mValue); } printf("]\n\n\n"); while(mFindValue!=999) { printf("Enter the number which you wanna find (if you want to exit it, enter '999' : "); scanf("%d", &mFindValue); if(mFindValue==999) { printf("\n\nExit................\n\n"); break; } else { /* SEARCH */ mIndex = BinarySearch(arr, 0, MAX_BUFF-1, mFindValue); if(mIndex < 0) { printf("There is no %d in this array. \n\n", mFindValue); } else { printf("\n%d is in Array[ %d ] and %d's KEY is %d\n\n", mFindValue, mIndex, mFindValue, arr[mIndex].mKey); } } } return 0; }
'IT > C - Programming' 카테고리의 다른 글
| [C코드] :: MULTITHREAD QUEUE code (멀티 스레드를 이용한 큐 코드) (3) | 2019.05.24 |
|---|---|
| [C개념] :: 자료형(Data type) 별 크기 및 범위 (0) | 2018.09.28 |
| [C코드] :: INSERTION SORT code (삽입 정렬 코드) (0) | 2018.03.27 |
| [C코드] :: Array based QUEUE code (배열 기반 큐 코드) (0) | 2018.03.26 |
| [C코드] :: Array based STACK code (배열 기반 스택 코드) (0) | 2018.03.21 |
차트
소소한 일상 C코드 DB 항상 행복하게^-^★
