1. 개요

정렬된 데이터에서 검색 범위를 줄여 나가면서 목적 값을 찾는 알고리즘이다. 데이터가 정렬되어 있을 경우, 데이터를 크기가 같은 두 부분으로 나누고 유효한 데이터집합을 선

1.1. 특징

• 루트 노드(상태)로부터 리프 노드(상태)까지 길이가 유한할 때만 사용가능하다.
• 노드 탐색 순서가 재귀적으로 표현될 때 적합하다.

2. 동작

1. 데이터의 중간 값을 찾는다.
2. 중간 값과 검색 값을 비교한다.
   1. 중간 값이 검색 값이 같을 경우, 종료한다.
   2. 중간 값이 검색 값보다 클 경우, 중간 값 기준 데이터의 왼쪽을 탐색한다.
   3. 중간 값이 검색 값보다 작을 경우, 중간 값 기준 데이터의 오른쪽을 탐색한다.
3. 데이터가 없을 경우 종료한다.

3. 시간 복잡도

O(logN) 데이터를 계속해서 이분하며 탐색해나간다.

4. 구현

• Python 코드
  단순히 모든 노드를 완전탐색하는 DFS 알고리즘이다.

    def binary_search (arr, val):
        first = 0
        last = len(arr) - 1
  
        # 데이터 범위가 있는 한 계속 탐색
        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   # 검색 값을 찾지 못했을 경우