0) 이진 검색 알고리즘이란 무엇입니까?
검색 영역을 절반으로 줄여 원하는 데이터를 빠르게 찾는 알고리즘
1) 순차 검색
이 장에서는 목록 내의 데이터를 매우 빠르게 탐색하는 방법을 배웁니다.
이진 검색 알고리즘대해 공부하겠습니다
이진 검색에 대해 알아보기 전에 가장 기본적인 검색 방법인 순차 검색에 대한 이해가 필요합니다.
순차 검색이란 무엇입니까? 목록에서 특정 데이터를 찾기 위해 데이터를 처음부터 하나씩 확인하는 방법(순차적 검색은 이름에서 알 수 있듯이 데이터를 순차적으로 검색하는 것을 의미합니다.
)
일반적으로 정렬되지 않은 목록에서 데이터를 찾아야 할 때 사용됩니다.
순차 검색 알고리즘의 장점은 목록에 아무리 많은 데이터가 있어도 시간만 있으면 원하는 항목(데이터)을 항상 찾을 수 있다는 점이다.
목록의 데이터를 하나씩 방문하여 특정 문자열과 일치하는지 확인하므로 구현도 간단합니다.
순차 검색은 매우 자주 사용되며, 또한 목록에 특정 값을 가진 요소가 존재하는지 in 연산자로 확인할 때 해당 요소를 순차적으로 검색한다.
하다, 목록 데이터 유형에서 주어진 값을 가진 요소 수 계산 계산하기() 메서드를 사용할 때 내부 검색도 순차적으로 수행됩니다.
# 순차 탐색 소스코드 구현
def sequential_search(n,target,array):
# 각 원소를 하나씩 확인하며
for i in range(n):
# 현재의 원소가 찾고자 하는 원소와 동일한 경우
if array(i) == target:
return i+1 # 현재의 위치 반환
print("생성할 원소 개수를 입력한 다음 한 칸 띄고 찾을 문자열을 입력하세요")
input_data = input().split()
n = int(input_data(0)) # 원소의 개수
target = input_data(1) # 찾고자 하는 문자열
print("앞서 적은 원소 개수만큼 문자열을 입력하세요. 구분은 띄어쓰기 한 칸으로 합니다.
")
array = input().split()
print(array)
print(sequential_search(n,target,array))따라서 순차탐색은 데이터의 정렬 여부와 상관없이 첫 번째 요소를 하나씩 살펴보는 성질을 갖는다.
따라서 데이터의 개수가 N일 때 최대 N번의 비교 연산이 필요하므로 순차 탐색의 시간 복잡도는 최악이다.
에)오전.
2) Binary Search: 이분법 검색
이진 검색은 배열 내의 데이터를 정렬할 때만 사용할 수 있는 알고리즘오전.
데이터가 랜덤인 경우에는 사용할 수 없으나, 이미 정렬되어 있는 경우 매우 빠르게 데이터를 찾는 특성이 있습니다.
이진 검색은 검색 영역을 반으로 좁혀서 데이터를 검색하는 기능있다
이진 검색은 위치를 나타내는 세 가지 변수를 사용합니다.
출발점수업 종점그리고 집중하다 오전.
이진 검색의 과정은 “찾을 데이터”와 “중간 데이터”를 반복적으로 비교하여 원하는 데이터를 찾는 것입니다.
이진 검색의 시간 복잡도는 검사할 항목의 수가 검사할 때마다 절반으로 줄어드는 것입니다.
오(logN)오전.
데이터를 반으로 자른다는 사실은 위에서 설명한 퀵 정렬과 공통점이 있습니다.
빠른 추가 설명으로 이진 검색 알고리즘은 평균적으로 단계를 반복할 때마다 확인하는 항목 수를 절반으로 줄입니다.
이진 검색을 구현하는 방법에는 두 가지가 있습니다.
‘재귀 함수’를 사용하는 방법그리고 다른 하나는 단순히 반복문 사용 방법오전.
2-1) 재귀함수 사용법
# 이진 탐색 소스코드 구현(재귀 함수)
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)2-2) 루프문을 사용하는 방법
# 이진 탐색 소스코드 구현(반복문)
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)