이진 탐색 알고리즘 ( Binary Search Algorithm )

선행 학습 : 분할 정복 알고리즘, 선형(순차) 탐색 알고리즘

 

 

 

안녕하세요~ 주말 아침부터 포스팅하네요.

 

아침부터 날씨가 좋네요 햇빛도 좋고~

 

근데 오후에 자외선이 너무 강하다 그래서 그게 좀 걸리네요.

 

썬크림 범벅하고 나가야 겠어요 ㅋㅋㅋ

 

자, 본론으로 들어가서 오늘은 이진 탐색 알고리즘에 대해서 알아볼 겁니다.

 

이진 탐색 알고리즘이란 이름에서 "이진"이라는 것은 학교 일진, 이진 이런게 아니구요 ㅡㅡㅋ

 

binary 라는 겁니다. 0 또는 1 로 숫자를 표현 할 때 이진수라고 하잖아요?

 

그 이진을 말하는 겁니다. 왜 이진 탐색이라는 알고리즘이 붙었을 까요?

 

그 이유는 알고리즘이 어떻게 동작하는지 그 원리를 알면 쉽게 이해가 됩니다.

 

자, 예제를 보면서 설명을 해볼게요.

 

아래 그림은 여러 숫자들이 작은 수부터 큰 수로 정렬이 되어있는 것을 보여주고 있습니다.

 

 

 

 

이진 탐색에서 중요한 것은 바로 이렇게 데이터 셋이 정렬이 되어있어야 한다는 것입니다. 

 

역순으로 정렬되어 있어도 상관없습니다. 순차적으로 정렬만 되어있으면 됩니다.

 

그리고 우리가 찾고자 하는 숫자는 바로 하늘색으로 칠해진 31이라는 숫자입니다.

 

이진 탐색 알고리즘은 데이터 셋의 처음부터 조회를 하는 것이 아니라 중간부터 조회를 시작합니다.

 

그 중간 지점은 point = low + ( low + high ) / 2 계산식으로부터 얻을 수 있습니다.

 

즉,  point = 0 + ( 9 - 0 ) / 2 니까 4가 되겠네요.

 

그럼 우리는 인덱스가 4인 곳의 값을 조회합니다. 그리고 우리가 찾고자 하는 데이터 31과 비교를 합니다.

 

27은 31이 아니고 31보다 작습니다. 

 

그리고 우리는 정렬된 데이터 셋을 이용하고 있으니까 인덱스가 4보다 작은 숫자들은 모두 31보다 작은 수 밖에 없을 것입니다.

 

그러니 그 쪽은 검색 대상에서 제외됩니다.

 

그러면 이제 새로운 point 를 계산하고 다시 31과 비교하는 식으로 과정을 반복하게 됩니다.

 

 

 

다음 포인트는 point = 5 + ( 9 - 5 ) / 2 = 7

 

 

 인덱스 7에는 35가 들어있네요. 31과 비교하니 큰 수이기 때문에 인덱스 7 이상의 데이터는 조회 대상에서 또 제외됩니다.

 

 

 

 

자, 이제 다음 point = 5 + ( 6 - 5 ) / 2 = 5 군요.

 

 

인덱스 5에 있는 값을 조회했더니 우리가 찾으려는 값과 동일한 값이 있네요!!! 

 

와하우~~~~~!!!! 드디어 찾았습니다!!!!

 

 

 

자, 몇번의 단계를 거쳐서 이 숫자를 찾은 건지 기억나세요??

 

네!!!! 맞습니다!!!! 단, 3번의 단계만에 우리가 찾고자 하는 숫자를 찾게 되었습니다.!!!!!

 

만약 이 데이터 셋을 가지고 선형(순차) 탐색을 했다면 몇 번 만에 원하는 값을 얻을 수 있었을 까요?

 

총 6번의 조회를 해야 원하는 값을 얻을 수 있었겠죠??? 

 

왜 그러냐구요? 잘 이해가 안되시면 선형(순차) 탐색 알고리즘 포스팅을 다시 한번 읽어보세요 ^-^

 

자, 다시 정리를 한번 해 봅시다.

 

이진 탐색은 정렬된 데이터 셋이 있어야 하고, 가운데 지점부터 조회를 하면서 원하는 데이터와 비교하고

 

그 결과에 따라 분할 정복 방식을 이용해서 조회를 필요로 하는 데이터 셋 사이즈를 1/2로 줄여나갑니다.

 

이 경우 시간복잡도는 O( log n ) 이 됩니다. 

 

선형(순차) 탐색의 시간복잡도 O(n)보다 평균적으로 빠른 속도를 자랑하죠.

 

 

 

이제 이진 탐색 알고리즘에 대해서 어느정도 개념이 잡히셨겠죠?

 

혼자만 알고있지 말고 친구들에게도 알려주세요 ^-^

 

그럼 이만 이진 탐색 알고리즘 포스팅을 마치도록 하겠습니다~~

 

좋은 하루 되세요~~