[python] 이진탐색

2023.04.27 - [코딩테스트] - [Python] 정렬 알고리즘 - 선택, 삽입, 퀵, 계수

[Python] 정렬 알고리즘 - 선택, 삽입, 퀵, 계수

 저번에 정렬 알고리즘에 이어서 이진탐색에 대해 알아보자..

 

 

이진탐색은 배열 내부의 데이터가 정렬되어있어야만 사용할 수 있다. 

이진 탐색은 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하므로 시간을 매우 단축시킬 수 있다.

시간복잡도는 O(log N)

 

 

1. 재귀함수를 이용한 이진탐색 구현 

def binary_search(array,target,start,end):
    if start>end:
        return None
    
    mid = (start+end)//2 #소수점 버린다

    if array[mid]>target: #기준이 타겟보다 크면 왼쪽만 탐색
        return binary_search(array,target,start,mid-1)
    
    if array[mid]<target: #반대면 오른쪽만 탐색
        return binary_search(array,target,mid+1,end)
    
    if array[mid] == target: #값 찾음
        return mid
    

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. 반복문을 이용한 이진탐색 구현

 

def binary_search(array,target,start,end):
    while start<=end:
        mid = (start+end)//2

        if array[mid]==target:
            return mid
        
        if array[mid] > target:
            end = mid-1
        
        if array[mid] < target :
            start = mid +1
        
    return None
    

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)

 

 

프로그램에서 데이터를 정렬해두는 경우가 많으므로 이진탐색을 효과적으로 사용 할 수 있다.

복잡하지 않지만 자주 사용하는 방식이니까 자주 연습하자~