내부 노드의 총 수를 n=2h- 1 으로 설정하면 의사 결정 트리는 깊이 h=lg(n+ 1) 의 전체 이진 트리 (깊이 h 에는 외부 노드가 포함되지 않음) 입니다. 나무의 K 계층 노드 수는 2k- 1 이며, 이를 찾는 데 필요한 비교 횟수는 K 이므로, 동일 확률 가정 하에서 이분법 성공 시 평균 검색 길이는 다음과 같습니다.
ASLbn≈lg(n+ 1)- 1
이진 검색이 실패하면 비교할 키워드 수가 의사 결정 트리의 깊이를 초과할 수 없으며 최악의 경우 비교 성공 수는 의사 결정 트리의 깊이를 초과할 수 없습니다. 즉:
이분 검색법의 최악의 표현은 평균 표현과 상당히 비슷하다.