C++ 재귀 이진 검색 (Recursive binary search) - 대학교 컴공 2학년 자료구조 과목

재귀 이진 검색이란 무엇인가

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을 반환한다.