이진 탐색

순차 탐색

- 데이터를 찾기 위해 앞에서부터 하나하나 차례대로 확인하는 방법

- WORST CASE 에는 O(N)

 

이진 탐색

- 데이터가 정렬되어 있을 때 사용 가능

- 매우 빠르게 데이터 탐색 가능

- 시작점,끝점 가운데의 중간점의 데이터와 찾고자 하는 데이터를 비교하여 범위를 좁혀나가는 방법

- 탐색 범위가 클 때(2000만을 넘거나 데이터 개수가 1000만 단위 이상이면)

 

재귀함수로 구현

data = [0,2,4,6,8,10,12,14,16,18]

def binary_search(start,end,val,data):
    mid = int((start + end)/2)
    #print(mid)
    if val == data[mid]:
        print("result:",mid)
        return mid
    elif val < data[mid]:
        #print("left", mid)
        return binary_search(start,mid-1,val,data)
    elif val > data[mid]:
        #print("right", mid)
        return binary_search(mid+1,end,val,data)

a=binary_search(0,9,4,data)
type(a)

 

반복문으로 구현

 

data = [0,2,4,6,8,10,12,14,16,18]

def binary_search(start,end,val,data):
    while start <= end:
        mid = (start+end)//2
        if val == data[mid]:
            return mid
        elif val < data[mid]:
            end = mid -1
        else:
            start = mid + 1
            
    return None

print(binary_search(0,9,4,data))

return을 밑에 두 재귀호출하는 부분에 안하니까 a 값이 안나오더라

재귀함수 실수 줄일 것(return을 타고 안에서부터 올라온다는 느낌)

 

이진 탐색 트리

- 부모 노드보다 왼쪽 자식 노드가 작고 오른쪽 자식 노드가 큼

- 1000만개를 넘어가거나 탐색 범위의 크기가 1000억 이상이라면 이진 탐색 알고리즘을 의심

 

문제 1. 부품 찾기  (난이도 1.5, 22분)

#6:35
N = int(input())
data = list(map(int,input().split()))
M = int(input())
order = list(map(int,input().split()))


def binary_search(array,start,end,val):
    while start <= end:
        mid = int((start + end)/2)
        if array[mid] == val:
            return "yes"
        elif array[mid] > val:
            end = mid - 1
        elif array[mid] < val:
            start = mid + 1

    return "no"


for i in order:
    print(binary_search(data,0,N-1,i),end=' ')

 

5분만에 다 짜놓고 뭐가 이상한지 모르다가 부등호 방향이 틀린걸 모르고있었음..

 

 

문제 2. 떡볶이 떡 만들기 (난이도 2, 완패)

#7:00
N,M = list(map(int,input().split()))
data = list(map(int,input().split()))

#정렬 10 15 17 19
#6만큼 필요하니까
#sum(list) - 17 * 4 < 6 <sum(list) - 15 * 4

#data = sorted(data)

start = 0
end = max(data)

#mid 최고, M 최저
result = 0
while start <= end:
    mid = (start + end) // 2
    size = 0
    for i in data:
        if i >= mid:
            size += i - mid
    if size < M:
        end = mid - 1

    else:
        start = mid + 1
        result = mid
        print(result)

 

길이를 좌표단위로 나뉘어 생각해서 이진 탐색으로 자를 부분의 최적의 위치를 찾아야하는 문제.

이진 탐색을 어디에 어떻게 써야하는지 감도 못 잡았고 처음엔 나름 최적화한 순차 탐색을 하려했지만 무조건 오답이었을 것.

나중에 다시 풀어보기.