이진 탐색(binary search)
- 메인 함수 : 1,2,3,4,7,8,11,15에서 11을 찾는 과정을 3가지 방법으로 구함
- 순차 탐색
- 이진 탐색(반복문 사용)
- 이진 탐색(재귀호출 사용)
12345678910111213int main(int argc, char** argv) {int A[8] = {1,2,3,5,7,9,11,15};int n = sizeof(A) / sizeof(A[0]);sequential_search(A, n, 11);binary_search_while(A, n, 11);int idx = binary_search_recursive(A, 11, 0, 7);printf("Search Index : %d\n", idx);return 0;} - 순차 탐색
1234567891011void sequential_search(int A[], int n, int k){ //sequential serachint idx=-1;for(int i=0; i<n; i++){if(k == A[i]){idx = i;}}printf("Search Index : %d\n", idx);}
- 이진 탐색(반복문 사용)
12345678910111213141516void binary_search_while(int A[], int n, int k){ //binary searchint s = 0, e = n-1, m; //s : start, e : end, m : midint idx=-1;while(e-s >= 0){m=(s + e) / 2;if(k == A[m]) {idx = m;break;}if(k > A[m]) s = m + 1;else e = m - 1;}printf("Search Index : %d\n", idx);}
- 이진 탐색(재귀 호출 Recursive 사용)
123456789int binary_search_recursive(int A[], int k, int s, int e){if(s > e) return -1;int m = (s + e)/2;if(k == A[m]) return m;if(k > A[m]) return binary_search_recursive(A, k, m+1, e);else return binary_search_recursive(A, k, s, m-1);}
