들어가기에 앞서 이진 탐색이나 이분 탐색이나 영어로는 Binary Search로 같은 말이다. 결국 데이터를 반으로 나누어가며 목푯값을 찾는 알고리즘이다. 여기서 말하는 데이터는 정렬된 배열을 말한다. 정렬된 배열로 진행해야 하는 이유는 이진 탐색 원리에 있다. 우선 시작점과 끝점을 가지고 중간점을 만든다. 중간값을 기준으로 원하는 값과 비교하여 탐색할 구간을 좁혀나간다. 원하는 값이 중간값보다 작으면 왼쪽 절반을 탐색하고, 더 크면 오른쪽 절반을 탐색한다. 위 작업을 반복하다가 원하는 값을 찾거나 구간이 사라지면 종료한다. 이진 탐색을 왜 사용할까? 배열을 처음부터 끝까지 차례대로 탐색하는 방법을 선형 탐색이라고 한다. 배열의 길이가 N이라고 할 때, 최악의 경우 시간복잡도는 O(N)이다. ..
