이분탐색(Binary Search)

이분탐색 알고리즘

이분탐색은 N개의 수가 크기 순서대로 배열되어 있을 때, 특정 k가 몇 번째 위치에 있는지 빠르게 찾는 방법이다. 

 

 

이해를 위해 예를 들어보자!

ex) 1부터 100까지 무작위 숫자 50개를 골라 정렬한 상태로 '13'을 찾아보자!

1~100까지 무작위 50개 숫자가 정렬된 상태

여기에서 첫 번째가 가르키는 배열의 인덱스를 start로 하고, 마지막 값을 가리키는 배열의 인덱스를 end로 하겠다. 저 숫자를 배열에 넣으면 

arr = [1, 2, ..., 26, ..., 28, 57, ...,86, ...,100] 으로 나타낼 수 있고,

arr[start] = 1, 

arr[end] = 100 으로 표기 할 수 있다.

 

여기서!! 중간 값을 가리키는 배열의 인덱스를 mid로 하면

arr[mid] = 28 이된다.

왜냐하면!! (start + end) / 2 = mid 이기 때문이다. (이해를 위해 첫번째 인덱스를 1로 설정) (1(start) + 50(end)) / 2 = 25(mid) 가 된다.

 

 

중간 값(28)이 찾으려는 수보다 크기 때문에 28이후의 숫자들은 시원하게 날려버린다~~ 한 마디로 arr[mid+1] 이후의 숫자들을 날리는 것이다.

28 이후 숫자들 빠이빠이~

그러면 배열에는 1부터 28까지의 숫자만 남게 된다.

arr = [1, 2, ..., 26, ..., 28] 이렇게 말이다.

end값을 mid 값으로 바꿔버리고!! 위와 같이 (start + end) / 2 = mid 를 하면 mid는 다음과 같이 14를 가리키게 된다.

 

 

인덱스 mid가 가리키는 값은 14

그러면 또 중간 값이 찾으려는 수보다 크기 때문에 14이후 숫자를 날려버린다~!~!~!

 

이렇게 계속 하다보면

중간값이 찾으려는 수보다 작으면 중간값 앞에 있는 수 제거

 

중간값이 찾으려는 수보다 작은 수를 만나게 된다. 그러면 그 숫자보다 앞에 있는 수들을 날리면 된다!!

 

어느새 숫자들이 줄고... 드디어 중간값이 찾으려는 수와 같게 된다!!!!! 꺄호오오오옭!!!!! 찾았다~~ 내사랑~~~ ㅋㅋㅋㅋ 

찾으려는 수를 만나게 된 오늘의 주인공

 

So easy!!! 이게 바로 이!분!탐!색! 정렬된 숫자들에서 찾고 싶은 수가 있다면!! 이!분!탐!색!

 

 

 

이분 탐색의 시간복잡도는 어떻게 될까?!

 

처음에 입력된 갯수를 N이라고 해보자!

첫 실행 후에는 

, 두 번째 실행 후는

, 세 번째 실행 후는

 가 된다.

그럼 k 번째 실행 후에는 

 이 된다! 이렇게 탐색을 반복하면 탐색이 끝나는 시점에는 남은 자료가 1개가 된다.

표기해보면, 

가 1이 된다. 이때 양변에 2^k를 곱해주면 다음과 같이 표기할 수 있다.

이것을 시간 복잡도로 나타내면,

로 나타낼 수 있다!

 

 

백준 이분탐색 문제 (10815 : 숫자카드)

 

 

a = int(input())
arr1 = list(map(int, input().split()))
a = int(input())
arr2 = list(map(int, input().split()))
ans = [0 for _ in range(len(arr2))] # 출력하는 배열 arr2 길이만큼 0으로 초기화
arr1.sort() # 정렬해줌

 # 이분탐색 알고리즘
for i in range(len(arr2)):
    left = 0
    right = len(arr1) - 1
    while left <= right:
        mid = (left + right)//2
        if arr1[mid] == arr2[i]: # 두 배열의 값이 같으면 ans를 1로
            ans[i] = 1
            break
        elif arr1[mid] > arr2[i]:
            right = mid-1
        else:
            left = mid + 1

for i in ans:
    print(i,end = " ")