[Python 기초] 탐색 (search)

#선형탐색 (Linear Search)

def linear_search(L,x):
    i=0 #index i를 0으로 준다
    while i < len(L) and L[i] != x: #i가 L리스트의 길이보다 작고, L의 i번째 원소가 x와 같지 않을때
        i += 1  #i를 1씩 증가시켜나간다.
#원소가 발견되면 i값을 가지고 loop가 종료하게 될 것이기 때문에 
#i가 L리스트의 길이보다 짧으면 리스트 안에서 원소를 발견했다는 의미
    if i < len(L): 
        return i  #발견된 x를 리턴하고
    else:
        return -1 #그렇지 않으면 -1을 리턴한다. 

 

S = [3,8,2,7,6,7,6,10,9]
linear_search(S,6)

#Out: 4

 

S = [3,8,2,7,6,7,6,10,9]
linear_search(S,1)
#Out: -1

 

 

 

 

#이진 탐색 (Binary Search)

-Divide & Conquer : 정렬되어 있을때만 가능 → O(log n)

 

#이미 정렬된 리스트 L에서 x를 이진 탐색으로 찾기
#리스트에 없을 경우 -1 반환
def solution(L, x):
    answer = -1
    lt=0 
    rt=len(L)-1 
    while lt<=rt:
        mid = (lt+rt)//2 
        if L[mid] == x: 
            answer = mid
            break
        elif L[mid]>x:
            rt=mid-1
        else: 
            lt=mid+1 
    return answer

 

 

 

 

 

#L 리스트 내 n개 숫자 중 target 위치를 이분 검색으로 찾기
n, target = map(int,input().split()) 
L = list(map(int,input().split()))
L.sort() #L을 순차로 정렬
lt=0 #lt는 가장 왼쪽 위치
rt=n-1 #lt는 가장 오른쪽 위치
while lt<=rt:
    mid = (lt+rt)//2 #중간 값을 구함 : 몫을 구함
    if L[mid] == target: #mid가 target이면 답을 찾은 것
        print(mid+1) #mid는 index(0번 부터 시작)이기 때문에 +1
        break
    elif L[mid]>target:
         #mid가 target보다 크면 lt...target..mid ...rt 
         #mid 왼쪽 탐색
        rt=mid-1 #mid index에서 -1함으로써 mid보다 큰 쪽을 다 날림. rt가 mid-1값으로 조정됨
    else: 
       #mid가 target보다 작면 lt.....mid ..target..rt
       #mid 오른쪽 탐색
        lt=mid+1 #mid위치에서 +1함으로써 mid+1위치부터 오른쪽으로 탐색
#Iput: 8 32
#Iput: 23 87 65 12 57 32 99 81
#Out: 3 (정렬 후의 결과이므로 작은 수로부터 3번째 큰 자리가 출력됨)