**이진 탐색 알고리즘(Binary search)**은 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 분환 정복(divide and conquer)방식 알고리즘이다. 각 단계에서 탐색 범위를 절반 씩 줄여가므로 시간 복잡도는 입력된 값이 n일때 O(log n)이다.

이진 탐색 알고리즘은 탐색 범위를 절반씩 좁혀가기 중간 값을 사용한다. 중간 값을 찾기 위해서는 데이터가 반드시 정렬되어 있어야 한다.

순차 탐색 알고리즘은 정렬되어 있지 않은 데이터에서도 탐색이 가능하다는 장점이 있지만 시간 복잡도가 O(n*2)이고 이진 탐색 알고리즘은 정렬된 데이터에서만 탐색이 가능하다는 단점이 있지만 시간 복잡도는 O(log n)으로 순차 탐색 알고리즘보다 빠르다는 장점이 있다.

동작방식

이진 탐색 알고리즘은 리스트의 중간 값과 비교하여 검색값을 찾습니다. 중간 값을 찾아야 하기 때문에 반드시 정렬된 배열에서만 사용할 수 있습니다.

• 배열의 중간값을 가져온 뒤 검색값(찾고자 하는 대상)과 비교합니다.
  • 중간값이 검색값과 같다면 종료 합니다. (mid == key)
  • 중간값보다 검색값이 크다면 중간값 기준 배열의 오른쪽 구간을 대상으로 탐색합니다. (mid < key)
  • 중간값보다 검색값이 작다면 중간값 기준 배열의 왼쪽 구간을 대상으로 탐색합니다. (mid > key)
• 값을 찾거나 간격이 비어있을 때까지 반복합니다.
• 2진 탐색은 찾고자 하는 값이 무엇인지 이진탐색을 통해서 어떻게 찾아갈 것인지 생각해보는 것이 필요하다.

이분 탐색 해결 가능한 문제 예시

• True혹은 False를 값으로 가지는 함수 F(i)가 있고,
• F(i) = False이면 i보다 작은 모든 i에서 F(i) = False일때,
• F(i) = True가 되는 i의 최솟값을 구하여라

존 벤틀리의 말에 따르면 제대로 이진 탐색 코드를 작성한 프로그래머는 10%내외라 할 정도로 실제 구현은 까다롭다. 코드가 짧으니 이진 탐색을 처음 접한 독자라면, 여러 차례 코드를 입력하며 자연스럽게 외워보자. 이진 탐색은 코딩 테스트에서 단골로 나오는 문제이니 가급적 외우길 권한다. <나동빈, 『이것이 코딩 테스트다』, p. 191.>

Python 이진 탐색 라이브러리

반복문을 이용한 구현

재귀 함수를 이용한 구현