N개의 데이터가 있을 때, 그 데이터를 차례대로 하나씩 확인하여 어떠한 처리를 해준 경우 → 순차 탐색
리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 차례대로 확인하는 방법
보통, 정렬되지 않은 리스트에서 데이터를 찾아야 할 때 사용함.
이진탐색은 배열 내부의 데이터가 정렬되어 있어야만 사용할 수 있는 알고리즘.
위치를 나타내는 변수 3개를 사용하는데 탐색하고자 하는 범위의 시작점, 끝점, 중간점
이다. 찾으려는 데이터의 중간점 위치에 있는 데이터를 반복적으로 비교해서 원하는 데이터를 찾는 게 이진 탐색 과정.
mid = (start + end) // 2
⇒ 중간점
#재귀 함수로 구현한 이진 탐색 코드
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)
10 7
1 3 5 7 9 11 13 15 17 19
4
10 7
1 3 5 6 9 11 13 15 17 19
원소가 존재하지 않습니
트리 자료구조는 노드와 노드의 연결로 표현하며 여기에서 노드는 정보의 단위로서 어떠한 정보를 가지고 있는 개체로 이해할 수 있음.
트리 자료구조는 그래프 자료구조의 일종으로 db 시스템이나 파일 시스템과 같은 곳에서 많은 양의 데이터를 관리하기 위한 목적으로 사용함.
루트 노드
라고 함.단말 노드
라고 함.⇒ 큰 데이터를 처리하는 sw는 대부분 데이터를 트리 잘구조로 저장해서 이진 탐색과 같은 탐색 기법을 이용해 빠르게 탐색이 가능함.
이진 탐색이 동작할 수 있도록 고안된, 효율적인 탐색이 가능한 자료구조.