바이너리 검색 횟수 비교

Question

표준 바이너리 검색 알고리즘에 대해이 재귀 코드를 작성했습니다. 비교 카운터에 언제 +1을 추가해야하는지 궁금합니다. 아래의 의사 코드

Inputs A: Array of Data; 
key:Data; L,R:Integer; 
Variables m:Integer; 
Returns m:Integer; 

Begin 
If R<L then return -1; fi 
m:= (R+L)/2 
if key = A[m] then return m; fi 
if key > A[m] then 
return binSearch(A,key,m+1,R); 
Else 
return binSearch(A,key,L,m-1); 
fi 
End 

첫 번째 if 문에서 L과 R을 비교하면 비교할 수 있습니까? 조금 혼란 스러웠다.

Answer 1

비대칭 분석에서 조건문은 O (1)로 간주됩니다.

조건부 문제는 의사 결정 문제이기 때문에. 0 또는 1입니다.

Answer 2

나는 당신이 비교할 때 엄밀히 말하면 얼마나 많은 ifs를 가지고 있을지 모르지만 대신에 바이너리 검색을 위해 O (log (n)) 복잡성에 도달하려고합니다. 이 경우 함수의 시작 부분에 셀 수는 없으므로 호출 횟수를 계산하십시오.