알고리즘 - 이진탐색 알고리즘 개념

안녕하세요.

오늘은 이진탐색 알고리즘 개념에 대해서 정리하려 합니다.

이진탐색이란 이진법, 이분법에서 파생된 말로 아메바를 예로 들 수가 있겠네요.

아메바는 번식을 할 때 자신의 몸을 반으로 나눠서 개체 수를 증가시킵니다.

그래서 사람들은 우수겟소리로 이분법적인 사고로 나눠서 판단하지 말라고도 말합니다.

두개로 분할한다라는 뜻으로 생각하시면 편할 것 같습니다.

 

그리고 이것을 수학적으로 접근해보면 우리는 친근한 게임을 예시로 들 수 있습니다.

그것은 바로 업다운 게임인데요.

우리는 업다운 게임을 할 때 본능적으로 가장 적은 횟수로 높은 확률을 갖을 수 있는 방법을 고안해 냅니다.

그것은 바로 1~100이란 숫자 중에 50을 기준으로 유추하기 시작하는 거죠.

만약 숫자가 87이라면 50을 묻고 높다고 판명이 되어 다시 75를 묻고 높다고 판명되어 이번엔 87를 묻고 정답을 맞추는 방법으로 단 3번만에 숫자를 맞출 수 있었습니다.

이러한 이진법을 이용한 수학적 접근을 알고리즘에서도 사용 할 수가 있습니다.

 

3 9 4 1 2 8 7 

7개의 수가 있고 이중에서 8을 찾아보겠습니다.

우선 순서대로 정렬을 해줍니다.

 

1 2 3 4 7 8 9

 

그 후 n/2번째 데이터를 8과 비교를 합니다.

그러면 4번째에 들어잇는 4와 비교를 하게 되고 4 < 8 임으로

1, 2, 4은 검색에서 제외되며 n의 범위는 5 ~ 7이 됩니다.

새롭게 정의된 n을 또 2로 나누어줍니다.

3/2 = 1 ...1 으로 6번째 인덱스 데이터를 비교해봅니다.

6번째의 인덱스에 들어있는 값은 8으로 찾고자 하는 데이터를 발견하였습니다.

이런 식으로 검색을 하면 단순히 for문을 n번 돌려서 찾는 것 보다 빠르고 효율적으로 탐색이 가능하게 됩니다.

 

 

우우우어어어어어~~~