[목차] == 개요 == Binary Search [[정렬]] 등과 함께 가장 기초인 [[알고리즘]]으로 꼽히는 문제. 검색 범위를 줄여 나가면서 원하는 데이터를 검색하는 알고리즘이다. == 상세 == 이진 탐색의 개념은 보통 대학교 1학년 프로그래밍 교재에 간단한 예제와 함께 소개되어 있는 경우도 있고, 분할과 정복의 쉬운 예제로 나오기도 한다. 이 알고리즘의 원리는 간단한 것으로 사전을 찾을 때 사전을 펴서 찾는 단어가 없으면 위치에 따라 앞쪽을 찾거나 뒤쪽을 찾고, 찾을 때까지 그걸 반복하는 걸 생각하면 쉽다. 단, 이진 탐색을 위해서는 자료가 순서에 따라 정렬되어 있어야 한다. 다음 그림은 이진 탐색으로 원하는 숫자 77을 찾는 과정이다. [[파일:5-18-1.png|width=300]] [[https://www.onlybook.co.kr/entry/algorithm-interview|<파이썬 알고리즘 인터뷰>]] p.516, 책만, 2020 먼저, 50부터 탐색을 시작한다. 77은 50보다 크므로 왼쪽 포인터를 오른쪽으로 이동한다. 그다음은 75다. 77은 75보다 크므로 마찬가지로 왼쪽 포인터를 오른쪽으로 이동한다. 다음은 87이다. 77은 87보다는 작으므로 이번에는 오른쪽 포인터를 왼쪽으로 이동한다. 이런 식으로 점점 범위를 좁혀 나가면 7번 이내에 무조건 숫자를 맞출 수 있게 된다. 마찬가지로 이 그림에서도 7번의 비교로 정답을 찾아냈다. 즉, {{{ function 이진탐색(데이터, 찾는 값) 데이터가 혹시 비어 있는가? (네) return 찾는 값 없음. 데이터의 가운데 지점을 찾는다. 찾은 지점의 값을 뽑는다. 뽑은 값이 찾는 값인가? (네) return 뽑은 값. (아니요) 뽑은 값과 찾는 값을 비교한다. (뽑은 값이 찾는 값보다 큰 값인가?) return 이진탐색(데이터 앞쪽 절반, 찾는 값) (작은 값인가?) return 이진탐색(데이터 뒤쪽 절반, 찾는 값) }}} {{{#!syntax cpp // 재귀적 이진 탐색의 C언어 예제 코드 int bSearch(T arr[], T val, int first, int last) { if (first > last) return -1; int mid = (first + last) / 2; if (val == arr[mid]) return mid; else if (val < arr[mid]) return bSearch(arr, val, first, mid - 1); else return bSearch(arr, val, mid + 1, last); } }}} {{{#!syntax python # 비재귀적 이진탐색의 Python 코드 def binary_search (arr, val): first, last = 0, arr.len() while first<=last: mid = (first + last) // 2 if arr[mid] == val: return mid if arr[mid] > val: last = mid - 1 else: first = mid+1 return -1 }}} 이렇게 된다[* 큰 값 작은 값 조건은 있는데 같은 값 조건이 없다고 생각하는 분은 알고리즘의 위쪽을 보라. 같은 값이면 찾는 값이다.]. 혹시 의사 코드를 못 읽는 사람을 위해 서술식으로 설명해보자면 주어진 리스트의 가운데 지점의 값을 비교해보고 그게 찾는 값보다 크면 뒤쪽 반을 잘라 버리고 작으면 앞쪽 절반을 잘라버린 다음에 그 '잘린' 리스트를 대상으로 똑같은 짓을 또 하는 것이다. 이게 원하는 값을 찾든지 아니면 다 버려버리든지(찾는 값 없음) 할 때까지 반복한다. 상기 코드들은 [[재귀함수]]로 구현되어 있다. 대부분의 이진 탐색은 비재귀로 구현되지만 그 본질은 이 재귀판 함수와 같다. 이진 탐색은 처음부터 끝까지 순서대로 찾는 순차 탐색에 비해 굉장히 빠르지만[* 이진 탐색의 계산복잡도는 O(logn), 순차 탐색이 O(n)이다.], 사전을 든 예시에서 볼 수 있듯이 '''미리 정렬이 되어 있어야 되는 점''', 경우에 따라서는 쓰기 곤란한 경우도 있다는 점이 단점이다. 이를테면 [[연결 리스트]]같은 것에 이진 탐색을 쓰기 곤란하다. 연결 리스트는 [[테이프]]같은 구조라 무작위 위치로 점프하질 못하고 앞뒤로 움직이기만 가능하기 때문이다. 물론 약간의 트릭을 쓰면 연결 리스트에서 이진 탐색이 가능하다. O(logn) 의 위력이 감이 잘 안온다면, 4,294,967,296개(약 43억개)의 원소가 있는 리스트에서 원하는 특정 값을 찾아낼 때 최악의 탐색 깊이(찾는 값이 없는 경우)는 딱 32회이다. 그러나 순차 탐색의 최악의 경우는 4,294,967,296회이다. 저게 0부터 순서대로 숫자가 들어있는 리스트라고 할 때 순차 탐색이 이진 탐색보다 빠른 지점은 32까지. 33부터 그 나머지 구간에서는 이진 탐색이 순차 탐색보다 빠르다. 33회의 비교시에는 약 86억개의 자료를 탐색할 수 있다. 우주에 존재하는 모든 원자 개수만큼의 원소를 가지는 리스트를 주어줘도 약 120회 정도만 비교하면 원하는 값을 찾을 수 있다. '뭐 하러 무식하게 일일이 비교하고 있나, 32를 찾고 싶으면 그냥 리스트의 32번째 원소를 읽으면 되지' 하고 생각하는 분은, 저게 그냥 예시라는 사실을 기억해주기 바란다. 어떤 데이터가 들어가 있는지 모르는 리스트에서 하나 알고 있는 건 그 리스트가 '''정렬돼''' 있다는 것뿐이다. 만약 어떤 데이터가 어떤 방식으로 들어가 있는지도 알고 있다면 이것보다 더 빠른 [[해시#s-2|해시 탐색]]을 사용할 수 있다. 해시 탐색의 시간복잡도는 O(1)이다. 말 그대로 리스트의 길이에 영향을 받지 않고 항상 일정한(상수)시간안에 찾아낸다. 아주 간략하게 예시를 들어보자. 대학생 여러분(특히 이러한 문서라면 높은 확률로 컴퓨터 관련 학과의 대학생)이라면 업다운이라는 술게임, 혹은 놀이를 해보았을것이다. 숫자 범위를 지정해놓고, 한 사람이 어떤 숫자를 마음속으로 생각하면, 맞추는 사람이 한가지 숫자를 던졌을 때 생각해 둔 숫자가 그 숫자보다 큰지, 혹은 작은지 알려주면서 점점 범위를 줄여 정답을 유추하는 놀이이다. 이 놀이에서 가장 빠르고 효율적으로 정답을 찾아내는 방법이 무엇일까? 바로 범위의 중간값에 위치한 수를 던지는 것이다. 범위가 1부터 100이라고 한다면 처음엔 50, 그보다 크다고 하면 75, 그보다 작다고 하면 62... 이런 식이다. 이 역시 이진 탐색의 한 가지 좋은 예시로서, 자연수는 기본적으로 개념 자체가 순서대로 정렬되어있는 개념이기 때문에 이것을 써먹을 수 있는 것이다. [[분류:탐색 알고리즘]]