[Python] 이진탐색 binary search

[ 개념 ]

 

- 맨 앞부터 스캔하여 순서대로 검색하는 선형탐색과 달리,

이진탐색은 우선, data가 sorting 되어있다는 가정 하에 탐색을 진행한다.

 

원리는 간단하다. 중앙 값을 선정하여 탐색의 범위를 좁혀나가는 것.

탐색하고자하는 key값이 중앙값 보다 크면 left의 값을 중앙값+1로, key값이 중앙값보다 작으면 right를 중앙값-1로..

이렇게 점차 탐색 범위를 줄여주는 것이다.

 

[ 적용 기준 ]

 

- 보통 어떤 x에 관해 함수 f(x)가 증가하거나 감소하는 함수일때  start,end를 x에 관한 최소값과 최대값으로 설정하여 이진 탐색으로 문제 해결

 

[ 코드 ]

#검색 대상은 반드시 오름 차순 정렬 되어있어야함!
#정렬 되어있다고 가정했을 때의 예제

from typing import Any,Sequence

def bin_search(k:Any,l_list:Sequence)-> Any:
    lp=0
    rp=len(l_list)-1
    
    
    while(1):
        mp=(rp+lp)//2
        if(l_list[mp]== k):
            print(f"찾았다!! {mp}번째에 있어요")
            break
            
        elif(l_list[mp]< k):
            lp=mp+1
           
        if(l_list[mp]> k):
            rp=mp-1            
            
        if (rp<lp):
            print("찾는 숫자 없음")
            break
                  
        
if __name__=='__main__':
    l_list=list(map(int,input().split())) #리스트 받음 (오름차순이라고 가정)      
    k=int(input("찾고 싶은 숫자는? "))    
    bin_search(k,l_list)
    
    
    
    

 

시간 복잡도는 O(logn)으로 굉장히 복잡도가 작은 편

 

<bisect>

 

- bisect.bisect(a,x,lo=0,hi=len(a))

- bisect_right() : x와 동일한 값이 존재하면, 값 바로 뒤 위치를 리턴함

- bisect_left() : x와 동일한 값이 존재하면, x와 동일한 값의 위치를 리턴함

- bisect.insort(a,x,lo=,hi=) : 오름차순으로 정렬된 시퀀스에 x를 삽입함