탐색 알고리즘이란

일반적으로 탐색은

• 주어진 데이터에서 특정 값을 찾고자 할 때
• 정렬되지 않은 데이터에서 max/min 값을 찾고자 할 때
• 그래프나 트리 구조에서 경로를 찾아야 할 때
• 데이터베이스에서 특정 레코드를 검색할 때

위와 같은 상황처럼 주어진 자료구조에서 원하는 항목을 찾기 위해 사용된다. 탐색하려는 대상 자료구조에 따라 다음과 같이 나눌 수 있다.

선형 탐색 (Linear Search)

• 가장 간단하면서 기본적인 탐색 알고리즘으로
• 리스트나 배열과 같은 자료구조에서 원하는 항목을 순차적으로 검색하는 방법
• 데이터를 처음부터 끝까지 한 칸씩 움직이면서 찾는 값과 하나하나 비교하며 동작
  

시간 복잡도는 O(n)으로, 리스트나 배열의 길이에 비례해 탐색 시간이 증가한다.
가장 간단한 방법으로 데이터가 정렬되어 있지 않거나 크기가 작은 경우에 사용할 수 있으며 데이터의 크기가 크거나 효율성이 중요한 경우에는 성능이 떨어진다.

이진 탐색 (Binary Search)

• 정렬된 배열을 가정하고, 정렬된 배열에서 중간 값과 비교하여 좌우로 좁혀가며 탐색
• 배열의 중간 값과 비교해 작으면 왼쪽 부분을, 중간 값보다 크면 오른쪽 부분을 대상으로 다시 탐색
  

구현 코드

def binarySearch(search_list, search, left=0, right=None):
	# 각각 왼쪽, 오른쪽 끝 인덱스를 나타내는 left, right
    if right is None:	# right 초기 설정
        right = len(search_list) - 1

    while left <= right:
        now = (left + right) // 2	# 중간 인덱스 now

        if search_list[now] < search:	# now 기준 오른쪽 부분 탐색
            left = now + 1
        elif search_list[now] > search:		# now 기준 왼쪽 부분 탐색
            right = now - 1
        else:
            return now
	
    return -1	# 찾으려는 값이 리스트에 없으면 -1 리턴

이진 탐색의 시간 복잡도는 O(log n)으로 탐색하고자 하는 데이터가 정렬되어 있고 대용량 데이터의 경우 효율적인 탐색 알고리즘이다. 하지만 정렬된 데이터에 새로운 데이터의 삽입/삭제가 필요한 경우 O(n)의 시간 복잡도를 갖기 때문에 데이터의 삽입/삭제가 빈번한 경우에는 경우 불리하다.