[Algorithm] 이진 탐색 (Binary Search)

나동빈님의 서적 '이것이 취업을 위한 코딩테스트다'를 읽고 정리하였습니다. 순차 탐색 순차 탐색은 가장 기본적인 탐색 방법이다. 대부분 자연스레 순차 탐색의 원리를 이해하고 있을 것이다. 순차 탐색(Sequential Search)이란 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 차례대로 확인하는 방법이다. 보통 정렬되지 않은 리스트에서 데이터를 찾아야 할 때 사용한다. 데이터 개수가 N개일 때 최대 N번의 비교 연산이 필요하므로 순차 탐색의 최악의 경우 시간 복잡도는 O(N)이다. 이진 탐색 이진 탐색(Binary Search)은 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 알고리즘이다. 탐색 과정 탐색하는 범위의 시작점, 끝점, 그리고 중간점을 두고 찾으려는 데이터와 중간..