[221220] 이분탐색과 시간복잡도

Q. 이분탐색이 무엇이고 시간복잡도는 어떻게 되며 그 이유는 무엇인가요?

👼 이분탐색이란

이분탐색이란, 정렬된 배열에서 특정 값을 찾는 탐색 알고리즘이다. 배열의 중간을 기준으로 데이터를 탐색하기 때문에 반드시 데이터가 정렬된 상태로 존재해야 한다.
이진 탐색의 시간 복잡도는 O(logN)으로 배열을 전수 조사하는 O(N)에 비하면 상대적으로 빠른 탐색 알고리즘에 속한다. O(logN)만에 값을 찾을 수 있는 이유는 중간을 기준으로 탐색 대상을 절반씩 줄여나가기 때문이다.

전체 데이터의 수를 N이라고 하자.

1) 첫 번째 탐색 후 절반만 남아 남은 수가 $N/2$개.

2) 두 번째 탐색에서 다시 절반만 남아 남은 수가 $N/2×1/2$개.

3) 세 번째 탐색에서 다시 절반이 남아 남은 수가 $N/2×1/2×1/2$개.

k) 규칙을 찾아보면 k번째 탐색에서 남은 데이터 수는 $(1/2)^k×N$이 된다.

최악의 경우에선$(1/2)^k×N=1$이 될 때까지 탐색을 하게 됨을 다시 한 번 기억하자.

위 식의 양변에 $2^k$를 곱하면 $2^k=N$가 되고 다시 양변에 $log2$를 취하면 최종 식은
$k=log2N$이 된다.

여기서 k는 탐색 횟수로 N에 따라 시행 횟수는 $logN$이 된다. 따라서 시간 복잡도는 $O(logN)$으로 나타낼 수 있다.

출처

[Algorithm] 이진 탐색 (이분 탐색, Binary Search) 코드와 시간 복잡도