이진 탐색(Binary Search)

• 오름 차순으로 정렬되어 있는 자료를 반으로 나누어 탐색하는 방법
• 자료를 중간값을 찾아 찾고자하는 값과 일치하는지 검사

동작 원리

1,2,3,4,5,6,7,8,9,10

• 위와 같이 오름 차순으로 정렬된 수열이 있고 우리고 찾고 싶은 값은 7이라고 생각해보자
• 우선 중간값을 찾아 7과 비교한다.

1,2,3,4,**5**,6,7,8,9,10

• 7은 5보다 크기 때문에 5보다 오른쪽에 있는 수열에서 같은 과정을 반복한다.

6,7,**8**,9,10

• 7은 8보다 작기 때문에 8보다 왼쪽에 있는 수열에서 같은 과정을 반복한다.

6,**7**

• 7 발견!
• 순차적으로 탐색하면 7번의 과정이 걸렸겠지만 이진 탐색을 사용하여 3번의 과정을 거쳐 찾아냈다.
• 이러한 이진 탐색은 자료의 크기가 커질수록 효율적으로 작동한다.
• 자료를 계속 반으로 나누어 중간값과 비교하기 때문에 시간복잡도는 O(log N)이 된다.

이진 탐색 구현

def binary_search(target, data):
    data.sort()
    start = 0 			# 맨 처음 위치
    end = len(data) - 1 	# 맨 마지막 위치

    while start <= end:
        mid = (start + end) // 2 # 중간값

        if data[mid] == target:
            return mid 		# target 위치 반환

        elif data[mid] > target: # target이 작으면 왼쪽을 더 탐색
            end = mid - 1
        else:                    # target이 크면 오른쪽을 더 탐색
            start = mid + 1
    return

DFS(Depth-First-Search, 깊이 우선 탐색)

• DFS는 그래프 탐색 알고리즘 중 하나로 그래프를 최대한 깊이 탐색한 뒤 최대 깊이에 도달했을 때 다음 노드로 이동하여 탐색하는 알고리즘 기법이다.