[Algorithm Tech] Binary Search(이분 탐색)

* Binary Search(이분 탐색)

이분 탐색은 정렬되어 있는 배열에서 값을 어떤 값(x)을 찾을때 사용할 수 있는 알고리즘이다.

기본 방법은, 정렬되어 있는 left와 right를 지정하여 배열의 중간 값(mid)을 구한다.

mid와 x를 비교했을 때, x가 더 크다면 left 값을 mid+1로 설정한다. (mid값 보다 오른쪽 검색)

mid와 x를 비교했을 때, mid가 더 크다면 right 값을 mid-1로 설정한다. (mid값 보다 왼쪽 검색)

위 과정을 반복하여 만족하는 값을 찾는 탐색 방식이다.

* 시간 복잡도

처음부터 끝까지 원하는 값을 찾을 때까지 탐색을 계속하는 순차 탐색은 Worst Case일 때 O(n)이라는 Time Complexity를 보여준다. 

10만개의 데이터가 있다면 무려 10만번을 탐색해야 하는 것이다. 

그러나, Binary Search는 탐색 대상을 절반씩 계속해서 줄여나가기 때문에, Worst Case일 때에도 탐색의 횟수가 log2n 이 되므로 10만개의 데이터가 있다고 하더라도 약 16번 정도로 탐색을 끝낼 수 있다. 

즉, 이분 탐색의 시간 복잡도는 O(logn)이다.