1. 범위를 반씩 좁혀가는 탐색

1) 순차 탐색

• Sequential Search, 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 차례대로 확인하는 방법.
• 리스트 자료형에서 특정한 값을 가지는 원소의 개수를 세는 count() 매서드를 이용할 때도 내부에서는 순차 탐색이 수행된다.

# 순차 탐색 소스코드 구현
def sequential_search(n, target, array):
	# 각 원소를 하나씩 확인하며
    for i in range(n):
    	# 현재의 원소가 찾고자 하는 원소와 동일할 경우
        if array[i] == target:
        	return i + 1 # 현재의 위치 반환(인덱스는 0부터 시작하므로 1 더하기)

print("생성할 원소 개수를 입력한 다음 한 칸 띄고 찾을 문자열을 입력하세요.")
input_data = input().split()
n = int(input_data[0]) # 원소의 개수
target = input_data[1] # 찾고자 하는 문자열

print("앞서 적은 원소 개수만큼 문자열을 입력하세요. 구분은 띄어쓰기 한 칸으로 합니다.")
array = input().split()

# 순차 탐색 수행 결과 출력
print(sequential_search(n, target, array))

생성할 원소 개수를 입력한 다음 한 칸 띄고 찾을 문자열을 입력하세요.
-> 5 Alex
앞서 적은 원소 개수만큼 문자열을 입력하세요. 구분은 띄어쓰기 한 칸으로 합니다.
-> Jason Nick Alex William Ray
-> 3

2) 이진 탐색 : 반으로 쪼개면서 탐색하기

• Binary Search, 배열 내부의 데이터가 정렬되어 있어야만 사용할 수 있는 알고리즘. 데이터가 무작위일 경우엔 사용할 수 없지만, 이미 정렬되어 있다면 매우 빠르게 데이터를 찾을 수 있다는 특징이 있음.
• 이진 탐색은 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 특징이 있음.
• 재귀 함수로 구현한 이진 탐색 코드

# 이진 탐색 소스코드 구현(재귀 함수)
def binary_search(array, target, start, end):
	if start > end:
    	return None
    mid = (start + end) // 2
    # 찾은 경우 중간점 인덱스 반환
    if array[mid] == target:
    	return mid
    # 중간점의 값보다 찾고자 하는 값이 작은 경우 왼쪽 확인
    elif array[mid] > target:
    	return binary_search(array, target, start, mid - 1)
    # 중간점의 값보다 찾고자 하는 값이 큰 경우 오른쪽 확인
    else:
    	return binary_search(array, target, mid + 1, end)
        
# n(원소의 개수)과 target(찾고자 하는 문자열)을 입력받기
n, target = list(map(int, input().split()))
# 전체 원소 입력받기
array = list(map(int, input().split()))

# 이진 탐색 수행 결과 출력
result = binary_search(array, target, 0, n - 1)
if result == None:
	print("원소가 존재하지 않습니다.")
else:
	print(result + 1)

• 반복문으로 구현한 이진 탐색 소스코드

# 이진 탐색 소스코드 구현(반복문)
def binary_search(array, target, start, end):
	while start <= end:
    	mid = (start + end) // 2
        # 찾은 경우 중간점 인덱스 반환
        if array[mid] == target:
        	return mid
        # 중간점의 값보다 찾고자 하는 값이 작은 경우 왼쪽 확인
        elif array[mid] > target:
        	end = mid - 1
        # 중간점의 값보다 찾고자 하는 값이 큰 경우 오른쪽 확인
        else:
        	start = mid + 1
    return None

# n(원소의 개수)과 target(찾고자 하는 문자열)을 입력받기
n, target = list(map(int, input().split()))
# 전체 원소 입력받기
array = list(map(int, input().split()))

# 이진 탐색 수행 결과 출력
result = binary_search(array, target, 0, n - 1)
if result == None:
	print("원소가 존재하지 않습니다.")
else:
	print(result + 1)

3) 트리 자료구조

• 노드와 노드의 연결로 표현하며 여기에서 노드는 정보의 단위로서 어떠한 정보를 가지고 있는 개체로 이해 가능
• 트리 자료구조의 특징
  

  • 트리는 부모 노드와 자식 노드의 관계로 표현된다.
  • 트리의 최상단 노드를 루트 노드라고 한다.
  • 트리의 최하단 노드를 단말 노드라고 한다.
  • 트리에서 일부를 떼어내도 트리 구조이며 이를 서브 트리라 한다.
  • 트리는 파일 시스템과 같이 계층적이고 정렬된 데이터를 다루기에 적합하다.

4) 이진 탐색 트리

• 이진 탐색이 동작할 수 있도록 고안된, 효율적인 탐색이 가능한 자료구조.
• 특징

  • 부모 노드보다 왼쪽 자식 노드가 작다
  • 부모 노드보다 오른쪽 자식 노드가 크다.