이진 탐색(Binary Search) 알고리즘이란? (JAVA)

안녕하세요? 코딩중독입니다.

 

저번 시간에는 선형 탐색에 대해 알아 보았습니다.

 

이번 시간에는 선형 탐색의 시간적 단점을 보완하는 이진 탐색 알고리즘을 공부해 봅시다.

 

 

이진 탐색은 무엇일까?

이진 탐색 알고리즘은 오름차순으로 정렬된 리스트에서 특정한 값의 위치를 찾는 알고리즘입니다.

 

처음 중간의 값을 임의의 값으로 선택하여, 그 값과 찾고자 하는 값의 크고 작음을 비교하는 방식을 사용합니다.

 

이 때, 처음 선택한 중앙값이 만약 찾는 값보다 크면 그 값은 새로운 최댓값이 되며, 작으면 그 값은 새로운 최솟값이 됩니다.

 

 

ㅎㅎ 글로만 보면 아직 감이 안잡히시죠? 그림을 통해 이해해 봅시다.

 

 

 

 

위와 같이 크기가 8인 배열이 있다고 하고, 찾으려는 값은 -7이라고 합시다.

 

 

 

 

처음에는 가장 중앙값을 고릅니다. (0 + 7) / 2 = 3.5이므로 3번째 인덱스의 값이 될 것입니다.

 

중앙값을 골랐다면, 그 값과 찾으려는 값이 같은지 비교해야 합니다.

 

제가 찾으려는 값은 -7이므로 중앙값보다 작습니다.

 

따라서, 중앙값 이상의 값은 볼 필요도 없으므로, 배열 내에 최댓값은 아래와 같이 -2가 됩니다.

 

 

 

 

이제, 남아 있는 [0, 2] 구간 중에서 중앙값을 고르고 찾으려는 값과 같은지 비교합니다.

 

 

 

 

중앙값은 (0 + 2) / 2 = 1이므로 1번째 인덱스인 -4가 될 것입니다.

 

이것은 제가 찾으려는 -7보다 크기 때문에 -4 이상의 값은 모두 볼 필요가 없게 되어, 배열 내에 최댓값은 -7이 됩니다.

 

 

 

 

배열의 요소는 1개만 남았으므로 중앙값은 당연히 -7이 되고, 이것은 우리가 찾으려는 값과 일치합니다.

 

따라서, 원하는 값을 찾았기 때문에 해당하는 위치를 출력하고 프로그램을 종료하면 됩니다.

 

 

선형 탐색의 시간 복잡도는 O(N)이었습니다. 과연, 이진 탐색의 시간 복잡도는 어떨까요?

 

배열의 크기를 N이라고 한다면, 첫 시행 후에는 반이 버려져서 탐색 횟수는 N / 2가  될 것입니다.

 

두 번째 시행 후에는 N / 4 가 될 것이고, k번째 시행 후에는 (1 / 2)^k * N이 됩니다.

 

결국, 최악의 경우에는 배열의 사이즈가 1이 될 때까지 반으로 쪼개는 것이므로 (1 / 2)^k * N = 1이고,  양변에 로그를 취하여 정리하면, log₂N이 되는 것을 알 수 있습니다.

 

따라서, 이진 탐색의 시간 복잡도는 O(logN) 입니다.

 

 

소스코드 - 반복문

 

 

소스코드 - 재귀

 

 

정리

이진 탐색은 선형 탐색보다 원리는 어렵지만, 실행 시간을 단축할 수 있다는 장점이 있습니다.

 

따라서, 다양한 알고리즘 문제에서 활용되기 때문에 반드시 숙지해야하는 알고리즘입니다.

 

처음에는 낯설더라도 꾸준히 연습하면 본인의 도구가 될 것입니다!

 

 

관련 문제

이분 탐색 문제집 (by cokcjswo)

 

 

지적 혹은 조언 환영합니다! 언제든지 댓글로 남겨주세요.

 

 

 

 

이 포스팅과 관련된 다른 글도 읽어 보세요.

 

[PS/이론] - 선형 탐색(Linear Search) 알고리즘은 무엇일까? (JAVA)

[PS/이론] - EOF의 사용 방법을 알아보자 (JAVA)

[PS/이론] - 당신이 PS에서 Scanner를 쓰면 안 되는 이유 (JAVA)