[05] 이진 탐색

리스트 내에 데이터를 매우 빠르게 탐색할 수 있음

 

순차 탐색(Sequential Search) :

리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 차례대로 확인하는 방법

 

리스트의 데이터에 하나씩 방문하며 특정한 문자열과 같은지 검사하므로 구현도 간단함

리스트에 특정 값의 원소가 있는지 체크할 때도 순차 탐색으로 원소를 확인하고, 리스트 자료형에서 특정한 값을 가지는 원소의 개수를 세는 count() 메서드를 이용할 때도 내부에선 순차 탐색 진행

 

순차 탐색 소스코드

def seq_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(seq_search(n, target, array))

순차 탐색은 데이터 정렬 여부와 상관없이 가장 앞에 있는 원소부터 하나씩 확인해야 한다

 

이진 탐색(Binary Search) :

배열 내부의 데이터가 정렬되어 있을 때 사용 가능

탐색 범위를 절반씩 좁혀가며 데이터를 탐색

 

위치를 나타내는 변수 3개 사용

시작점 / 끝점 / 중간점

찾으려는 데이터와 중간점 위치의 데이터를 반복적으로 비교하여 원하는 데이터를 찾음

 

한 번 확인할 때 확인하는 원소의 개수가 절반씩 줄어든다.

 

재귀 함수로 구현한 이진 탐색

# 이진 탐색 소스코드 구현(재귀함수)
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) # 인덱스는 0부터 시작하므로 +1 반환

 

반복문으로 구현한 이진 탐색

# 이진 탐색 소스코드 구현(반복문)
def binary_search(array, target, start, end):
	while start <= end:
    	mid = (start + end) // 2
        # 찾은 경우 중간점 인덱스 반환
        if array[mid] == target:
        	return min
        # 중간점의 값보다 찾고자 하는 값이 적은 경우 왼쪽
        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)