[ 알고리즘 ] 이진탐색

방법

1. 첫번째 인덱스와 마지막 인덱스의 값을 합한 후 절반으로 나눈다.
2. 절반으로 나눠 나온 중앙 인덱스의 값과 target 값을 비교한다.
3. 만약 target 값보다 작다면 왼쪽을 크다면, 오른쪽을 탐색한다.

그럼, 언제까지 이 탐색을 반복해야 할까?

탐색하는 first와 last 값이 만날 때까지?

first와 last 값이 만났다는 것은 비교할 대상이 하나 남았다는 것이다.(first와 last가 만났을 떄의 값도 비교해야함)

이진탐색의 탐색횟수를 계산해보자

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

1. n을 1이 될 때 까지 나눈다.
2. 데이터가 1개남았을 때, 이때 마지막으로 비교연산 1회 진행

즉, 수식으로 표현하면

수식을 정리하면 아래와 같다.

정리된 최종 수식의 양 변에 밑이 2인 로그를 취하면 아래와 같이 된다.

즉, 이진탐색은 logn의 시간복잡도를 가지는 알고리즘이라고 할 수 있다.