탐색

이번 시간에는 탐색 중 많이 사용되는 이분탐색에 대해 포스트한다.
그 전에 일반적으로 알고 있는 탐색 방법에는 선형탐색(linear search)이 있다.
데이터의 처음부터 끝까지 탐색하는 방법인데, 이는 데이터의 갯수가 늘어남에 따라 탐색시간이 일정하게 늘어나는 단점이 있다.
생각해보자. 데이터의 갯수가 100,000 , 10,000,000개 이상 늘어난다면 탐색하는 시간이 그만큼 길어진다.

<그림1 O(n)>

이 단점을 보완하기 위해 이분탐색(binary search)가 등장했다.

이분 탐색

데이터의 중간값부터 검색하여 일치하는 데이터가 없는 절반은 탐색하지 않는 탐색 방법

이전에 포스트했던 업다운 게임을 예를 들어보자
임의의 숫자를 찾기 위해 1부터 100까지 전부 순서대로 찾아보는 방법이 있고,
처음에 50 -> 임의의 숫자에 따라 75 or 25 ...처럼 찾아간다면 훨씬 빠르게 찾을 수 있을 것이다. 실제로 업다운 게임에서 해당 숫자를 찾을 최대 횟수는 log_2(100) = 6.64... 약 7회 이다.

<그림2 O(logn)>

<그림3 O(n)과 O(logn) 비교>

조건

이분 탐색을 하기 위해서는 데이터가 모두 정렬이 완료되어있어야만 한다.
데이터의 절반 씩 탐색하지 않아도 되는 이유는 데이터가 정렬되어있기 때문!