이진 탐색(Binary Search) 개념 & 구현

" 이것이 코딩테스트다 (with.python) 나동빈님의 책을 참고하여 작성되었습니다"

순차탐색 

---

순차탐색이란 ?

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

 

# 소스코드

def sequential_search(n, target, array):
    for i in range(n):
        if array[i] ==target:
            return i+1 #현재 위치 반환
    
input_data=input().split()
n = int(input_data[0])
target = input_data[1]

array=input().split()

print(sequential_search(n,target,array))

데이터의 정렬 여부와 관계없이 가장 앞에 있는 원소부터 하나씩 확인함

데이터의 개수가 N개 일때 최대 N번의 비교 연산이 필요함으로 최악의 경우 시간복잡도는 O(N)이다.

 

이진탐색

---

• 배열 내부의 데이터가 정렬 되어야함
• 탐색 범위를 절반씩 좁혀가면서 데이터를 탐색함
• 시작점 ,끝점 ,중간점을 나타내는 변수 3개를 사용
• 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교
• 시간복잡도 O(logN)

소스코드

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, end-1)
    else:
        return binary_search(array, target, start-1,end)

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)

 

https://search.shopping.naver.com/book/catalog/32441237189