단순 Binary Search 코드이다. 정렬된 배열에서 특정 값을 찾는 효율적인 알고리즘이다. 검색 범위를 절반씩 줄여나가면서 목표 값을 찾는다. l = 0, r = n-1으로 초기화한 다음에, 중간 값을 찾아서, 범위를 좁혀나간다. a[m] > x 인 경우, 즉 m의 배열값이 x보다 큰 경우 r = m-1로 설정한다. (0~m-1 탐색) a[m] < x 인 경우, 즉 m의 배열값이 x보다 작은 경우 l = m+1로 설정한다. (m+1 ~ n-1 탐색)
증명 (Proof by Invariant)
invariant는 불변 법칙이다. invariant를 설정하고, invariant가 깨지지 않음을 통해 증명한다. a[i] = x 라면, i는 l과 r의 인덱스 범위 안에 무조건 있을 것이다. 이는 l과 r이 아무리 변해도, a[i] = x인 i는 l과 r의 인덱스 범위 안에 무조건 있기 때문이다.
2. Recursive Binary Search
Recursive Binary Search
이진 탐색 트리를 재귀 코드로 표현한 것이다. a[]는 정렬된 탐색할 배열, n는 배열의 길이(검색 범위), x는 우리가 찾을 값이다. Base Condition(종료 조건)은 n <=0 인 경우, 즉 탐색할 배열의 길이(검색 범위)가 0이하인 경우 -1을 리턴한다. m = n/2를 통해, m 변수에 검색 범위의 중간 인덱스를 계산하여 저장한다.
1. a[m] == x 인 경우, 정답이니 정답 인덱스 m을 반환한다. 2. a[m] > x 인 경우, (0~m-1) 범위만 찾아야 되니, search(a, m, x)를 호출한다. 3. a[m] < x 인 경우, (m+1 ~ n-1) 범위만 찾아야 하니, 배열의 시작 주소를 a+m+1로 설정하고, 배열의 길이(검색 범위)를 n-m-1로 설정하고 탐색한다. return r + m + 1을 해줘야 한다. (m+1 부터 탐색을 시작했기 떄문)
2. 증명 Proof by Induction(수학적 귀납법)
수학적 귀납법으로 증명을 할 수 있다. Base n = 0 인 경우, a[i] = x가 성립할 방법이 없고, -1을 리턴한다. Step - case 1. a[m] = x 인 경우, M을 리턴하므로 성립한다. - case 2. a[m] > x 인 경우, a[m] ~ a[n] 사이에는 x는 없으므로, i는 0 ~ m-1 사이에 하나이다. search(a, m, x) 성립 - case 3. a[m] < x 인 경우, a[0] ~ a[m] 사이에는 x는 없으므로, i는 m+1 ~ n 사이에 하나이다. search(a+m+1, r-m-1, x) 성립
2. 시간 복잡도 (recursive binary search)
재귀적 이진 탐색의 시간 복잡도 설명 재귀적 이진 탐색의 시간 복잡도는 O(log n) 이다.
재귀적 이진 탐색은 각 단계에서 검색 범위를 절반으로 줄인다. 즉, 배열의 중간 요소를 확인하고 대상 값이 중간 값보다 큰지 작은지에 따라 왼쪽 또는 오른쪽 절반에서만 검색을 계속한다.
로그 함수: 검색 범위를 절반으로 줄이는 과정은 로그 함수와 유사합니다. 배열의 크기가 n일 때, 최대 logn 번의 단계를 거쳐 검색 범위가 1로 줄어든다.
