파이썬(python) : 이진탐색 aka. 이분탐색(binary search)

binary search 알고리즘은 번역해서 이진 탐색이라고도 부르고, 이분 탐색이라고도 부른다.

• 이진 탐색(이분 탐색) 알고리즘은 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법이다.
• 이진 탐색은 배열 내부의 데이터가 정렬되어 있어야만 사용할 수 있는 알고리즘이다.
• 변수 3개(start, end, mid)를 사용하여 탐색한다. 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교해서 원하는 데이터를 찾는 것이 이진 탐색의 과정이다.

즉!!

1. 원소가 정렬이 되어 있을 것(오름차순이든 내림차순이든)
2. 원소의 Random Access가 가능해야 한다.

그리고 만약, 중복되는 원소가 있다면, 일반적인 binary search가 아닌, upper_bound와 lower_bound를 각각 구한 뒤, lower_bound부터 upper_bound직전까지 다 훑으면, 해당 크기의 모든 원소를 확인할 수 있다. 원소가 중복이 있는지 아닌지도 구현시 디테일을 바꾸게 하는 하나의 체크 포인트이다.

이진탐색을 구현하는 방법에는 2가지가 있는데 하나는 재귀 함수를 이용한 방법이고,

다른 하나는 단순하게 반복문을 이용하는 방법이다.

 

<재귀함수를 이용한 코드>

#이진 탐색 소스코드 구현(재귀함수)
def binary_search(array, target, start, end):
    if start > end :
        return None

    mid = (start + end)//2

    if array[mid] == target:
        return mid
    # 찾고자 하는 값이 mid와 같다면 mid 를 return(출력)
    elif array[mid] > target :
        return binary_search(array, target, start, mid-1)
    # mid 값보다 찾고자 하는 값이 작다면 mid 값의 왼쪽 확인
    else:
        return binary_search(array, target, mid + 1 , end)
    # mid 값보다 찾고자 하는 값이 크다면 mid 값의 오른쪽 확인

# n(원소의 개수)과 target(찾고자 하는 값)을 입력 받기
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(result + 1)

<반복문을 이용한 코드>

#이진 탐색 소스코드 구현(반복문)
def binarySearch(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(찾고자 하는 값)을 입력 받기
n, target = list(map(int, input().split()))
# 전체 원소 입력 받기
array = list(map(int, input().split()))

# 이진 탐색 수행 결과 출력
result = binarySearch(array, target, 0, n - 1)
if result == None:
    print("원소가 존재하지 않습니다.")
else:
    print(result + 1)