[알고리즘] 이분 탐색

이분탐색은 탐색을 반복할수록 탐색할 대상이 1/2가 되는 알고리즘이다.

따라서 시간 복잡도는 O(logN)이다.

이분 탐색은 "반드시 정렬된 상태"에서 시작되어야 한다.

 

파이썬으로의 구현은 재귀, 비재귀 방법이 있다. 

우선 비재귀를 살펴보자.

---

비재귀 방법

import sys
n=int(sys.stdin.readline())
arr_n = list(map(int,sys.stdin.readline().split()))
m=int(sys.stdin.readline())
arr_m = list(map(int,sys.stdin.readline().split()))
arr_n.sort()

for i in range(m):
    left = 0
    right = len(arr_n)-1
    while left<=right:
        mid = (left+right)//2
        if arr_m[i] == arr_n[mid]:
            print(1)
            break
        elif arr_m[i]<arr_n[mid]:
            right = mid-1
        else:
            left = mid+1
    if left>right:
        print(0)

 

다음은 arr_m의 숫자들이 arr_n에 존재하는지 판단하는 문제이다.

보다시피 arr_n을 정렬하고, left(혹은 start), right(혹은 end), mid를 활용한다.

---

재귀 사용 방법

# data는 오름차순으로 정렬된 리스트
def binary_search_recursion(target, start, end, data):
    if start > end:
        return None

    mid = (start + end) // 2

    if data[mid] == target:
        return mid
    elif data[mid] > target:
        end = mid - 1
    else:
        start = mid + 1        

    return binary_search_recursion(target, start, end, data)

# 테스트용 코드
if __name__ == '__main__':
    li = [i*3 for i in range(11)]
    target = 6
    idx = binary_search_recursion(target, 0, 10, li)

    print(li)
    print(idx)

이 코드는 출처에서 가져온 코드이다.

---

다음은 백준 이진 탐색 관련 문제 풀이들이다.

1. #1920 수 찾기

https://live-for-myself.tistory.com/208

[CodingTest] 백준 #1920 수 찾기

 

2. 숫자 카드 2

https://live-for-myself.tistory.com/222

[CodingTest] 백준 #10816 숫자 카드 2

---

출처 : https://wayhome25.github.io/cs/2017/04/15/cs-16/