알고리즘 - 이진 탐색 알고리즘 (Binary Search algorithm)

 

 

 

이진 탐색 알고리즘이란?

정렬되어 있는 리스트에서 특정한 데이터를 빠르게 탐색할 수 있게 해주는 탐색 알고리즘이다.

- 기본적으로 별다른 말이 없다면 순차 탐색을 이용한다고 본다.

- 이진 탐색은 정렬되어 있는 리스트에서 절반씩 범위를 줄여가며 데이터를 탐색하는 방법으로 빠르게(=시간 복잡도가 낮다) 진행 가능하다.

 

 

 

<이진 탐색 동작 예시>

- index[0] 시작점 

- index[4] 중간점

- index[9] 끝점

 

<이진 탐색의 시간 복잡도>

 

<재귀 함수를 이용해서 이진 탐색을 구현한 소스코드>

#이진 탐색 소스코드 구현( 재귀 함수를 이용해서 )

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 = list(map(int,input().split()))

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

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

if result == None:
    print('원소가 존재하지 않습니다.')
else:
    print(f'찾고자하는 수 {target}은(는) {result + 1}번째에 존재합니다.')

 

<반복문을 통해서 이진 탐색을 구현한 소스코드>

#이진 탐색 소스코드 구현( 반복문을 이용해서 )

def binary_search(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 = list(map(int,input().split()))

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

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

if result == None:
    print('원소가 존재하지 않습니다.')
else:
    print(f'찾고자하는 수 {target}은(는) {result + 1}번째에 존재합니다.')

 

 

<코딩테스트를 위한 파이썬 이진 탐색 라이브러리>

 

 

<값이 특정 범위에 속하는 데이터 개수 구하기>

from bisect import bisect_left, bisect_right

#값이 left_value, right_value인 데이터의 개수를 반환하는 함수
def count_by_range(a,left_value, right_value):
    right_index = bisect_right(a,right_value)
    left_index = bisect_left(a,left_value)
    return right_index - left_index

#배열 선언
a = [1,2,3,3,3,3,4,4,8,9]

#값이 4인 데이터 개수 출력
print(count_by_range(a,4,4))

#값이 [-1, 3] 범위에 있는 데이터 개수 출력
# -1이상 3이하의 값이 몇개인지 출력
print(count_by_range(a,-1,3))

 

 

<파라메트릭 서치(Parametric Search)>

- 파라메트릭 서치란 최적화 문제를 결정 문제('예' 혹은 '아니오')로 바꾸어 해결하는 기법이다.

      - 최적화 문제란?

        어떤 함수의 값을 가능한 가장 낮추거나 가장 크게 높히거나 하는 문제이다.

      - 예시: 특정한 조건을 만족하는 가장 알맞은 값을 빠르게 찾는 최적화 문제

- 일반적으로 코딩 테스트에서 파라메트릭 서치 문제는 이진 탐색을 이용해서 해결할 수 있다.