[자료구조 및 알고리즘] 이진탐색 (Binary Search)

이진탐색

 

이진탐색은 정렬되어 있는 리스트에서 탐색 범위를 절반씩 줄여가며 데이터를 탐색하는 방법이다. 시작점 끝점을 이용해 탐색범위를 결정한다. 단계마다 탐색 범위를 2로 나누는 것과 동일하므로 연산횟수는 logn에 비례한다. O(logN)을 보장해준다.

 

이진탐색은 위치를 나타내는 변수 3개를 이용한다. 시작점, 중간점, 끝점 -> 중간점이 실수인 경우, 버림한다.

 

중간값에 있는 데이터와 찾고자하는 값을 비교한 후, 크냐 작으냐에 따라 중간점 + 1, 중간점 - 1 값을 시작점 또는 끝점으로 변경한 후 다시 중간점을 찾는다. 이후 값을 찾거나 탈출조건에 해당할 때까지 위 과정을 반복한다.

 

구현 방법

 

반복문, 재귀함수

 

기억해야 할 것

 

이진탐색은 정렬된 리스트에서만 사용가능한 알고리즘이다. 따라서 이진탐색을 사용하려면 리스트를 정렬한 후 사용하도록 하자. 처리해야할 데이터의 개수가 1000만 이상이 되면 O(logN)의 속도를 내는 알고리즘을 떠올리는 게 좋다.

 

코드

 

# 재귀함수를 이용해 구현

def binary_search(array, target, start, end):
    if start > end : return None

    mid = (start+end)//2
    # 찾은 경우 중간점 인덱스 반환
    if array[mid] == target: return mid
    # 중간점의 값보다 찾고자 하는 값이 작은 경우 왼쪽 확인
    elif array[mid] > target: return binary_search(array, target, start, mid-1)
    # 중간점의 값보다 찾고자 하는 값이 큰 경우 오른쪽 확인
    else: return binary_search(array, target, mid+1, end)

n, target = map(int, input().split())
array = list(map(int,input().split()))

result = binary_search(array, target, 0, n-1)

if result == None: print("원소가 존재하지 않습니다.")
else: print(result+1)

# 반복문을 이용해 구현

def binary_search_loop(array, target, start, end):
    while start <= end:
        mid = (start + end) // 2
        if array[mid] == target: return mid

        elif array[mid] > target:
            end = mid -1
        else: start = mid + 1
    return None

n, target = map(int, input().split())
array = list(map(int,input().split()))

result = binary_search_loop(array, target, 0, n-1)

if result == None: print("원소가 존재하지 않습니다.")
else: print(result+1)

주의

 

1. lo, hi는 항상 정답의 범위를 나타낼 수 있도록 해야합니다. 예를 들어 lo를 출력해야 하는 문제의 답이 최대 n일 때 hi = n으로 선언하거나, hi를 출력해야 하는 문제의 답이 최소 0일 때 lo = 0으로 선언하면 안됩니다. (hi = n + 1, lo = -1로 선언해야 합니다)
2. 오버플로우에 주의해야 합니다. 이분 탐색을 사용하는 문제는 대부분 수의 범위가 크기 때문에 오버플로우가 발생할 수 있습니다.
3. 결정 문제의 정의에 맞게 Check함수를 잘 구현해야 합니다. 예를 들어 lower_bound는 v[i] >= k인 i의 최솟값을 구하는 함수이고, upper_bound는 v[i] > k인 i의 최솟값을 구하는 함수인데, Check 함수의 부등호를 조금만 틀려도 전혀 엉뚱한 값이 튀어나올 수 있습니다.

출처 : https://www.acmicpc.net/blog/view/109

이분 탐색(Binary Search) 헷갈리지 않게 구현하기