[JAVA] 이진 탐색 (Binary Search)

조건 : 탐색 전 배열이 정렬되야한다.

 

시간 복잡도 = log₂ N

"데이터의 수가 n일 때, 최악의 경우에 발생하는 비교연산의 횟수는?"

데이터의 수 n이 n/2, n/4, n/8 ... 줄어서 1이 될 때까지 비교연산을 한 번씩 진행하고, 마지막으로 n이 1일 때 비교연산을 한 번 더 진행하게 된다. 그리고 그것이 탐색 대상이 존재하지 않는 최악의 경우의 비교연산 횟수이다.