반응형
재귀 이진 검색이란 무엇인가
2023.10.23 - [코딩 data lab] - 이진 검색(binary search)이란 무엇일까? - 대학교 컴공 2학년 자료구조 과목
재귀 이진 검색은, 전 게시물에서 다루었던 이진 검색을 재귀함수의 형식으로 구현할 수 있도록 만든 알고리즘이다.
수업에 나온 예시코드
int rbs(int* a, const int x, const int left, const int right) {
if (left <= right) {
int middle = (left + right) / 2;
if (x < a[middle]) return rbs(a, x, left, middle - 1);
else if (x > a[middle]) return rbs(a, x, middle + 1, right);
else return middle;
}
return -1;
}
코드 분석
구하고자 하는 x의 값이 a[middle]보다 작을 경우에는 right의 값을 middle-1 로 변경하여 다음에 시행되는 반복연산에서는 왼쪽 토막을 대상으로 시행되도록 재조정한다. x의 값이 a[middle]보다 클 경우 left의 값을 middle+1로 변경해 오른쪽 토막을 대상으로 시행되도록 재조정한다. x가 a[middle]과 같으면 middle을 반환하고, 세 경우 전부 아니면 -1을 반환한다.
반응형
'data lab' 카테고리의 다른 글
C++ 포인터 개념 잡기 - 배열 관련 개념 (0) | 2023.10.26 |
---|---|
C++ 순열(permutation) - 대학교 컴공 2학년 자료구조 과목 (0) | 2023.10.25 |
C++ 이진 검색(binary search)이란 무엇일까? - 대학교 컴공 2학년 자료구조 과목 (0) | 2023.10.23 |
C++ 선택정렬 (selection sort)이란 무엇일까? - 대학교 컴공 2학년 자료구조 과목 (0) | 2023.10.22 |
23년 9월 22일 사업을 시작했습니다. (0) | 2023.09.28 |