이진탐색 (feat. 백준 1920)

https://www.acmicpc.net/problem/1920

풀다가 이진 탐색 알고리즘을 구현하는 중에 막혔던 부분이 있어서 관련 글을 좀 더 찾아 정리한다. 

 

 

left = 0
right = N - 1
mid = int((left + right)/2)
find = False
while left <= right:
    #print(b, '>>', left, right, mid)
    if b == A[mid]:
        find = True 
        break
    elif b > A[mid]:
        left = mid + 1
    elif b < A[mid]:
        right = mid - 1 

    mid = int((left + right)/2)
    #print(mid)

if find == True:
    print(1)
else:
    print(0)

- left와 right를 조정해서 원하는 값이 나올때까지 돌린다는 것은 어렴풋이 기억났다. 그래서 이 부분 구현까지는 어렵지 않았다. 

- while 문을 나가는 조건을 처음에는 계속 mid가 나누고 나누는 값이다 보니 mid > 0 일때까지 돌리면 된다고 생각을 했다. 

- 그래도 돌아가기는 하지만, 불필요한 반복문이 생기는 거다 보니 left <= right 을 해야 정상적으로 종료가 된다는 것을 배웠다. 

 

시간복잡도는 다음과 같다. 

- 최선: O(1)

- 평균: O(log N)

- 최악: O(log N)

 

 

 

참고 >>

- 나무위키 '이진 탐색' - https://namu.wiki/w/%EC%9D%B4%EC%A7%84%20%ED%83%90%EC%83%89

- [Algorithm] 이진 탐색(Binary Search)과 시간복잡도 - https://bkstudio.tistory.com/10