[Algorithm] 이진 탐색 (Binary Search)

이진 탐색과 순차 탐색

---

• 일단, 이진 탐색과 순차 탐색을 비교해봅시다.

종류	설명
이진 탐색	정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법 이진 탐색은 시작점, 끝점, 중간점을 이용하여 탐색 범위를 설정
순차 탐색	리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 확인하는 방법

• 이진 탐색은 이처럼 탐색 범위를 좁혀 나가기 때문에 순차 탐색보다 더 적은 시간 복잡도를 가질 수 있습니다.

---

이진 탐색 동작 예시

---

• 아래와 같이, 이미 정렬된 10개의 데이터 중에서 값이 4인 원소를 찾는 예시를 확인해보겠습니다.

[Step 1]

•  시작점 : 0, 중간점 : 8, 끝점 : 18 (소수점 이하는 제거)로 지정할 수 있습니다.
•  찾고자 하는 값보다 중간점의 위치의 값이 크다면 중간점부터 끝점까지의 데이터는 확인할 필요가 없습니다.
•  따라서, 중간점의 왼쪽 데이터로 끝점을 옮기고 다시 시작점, 중간점, 끝점을 정합니다.

[Step 2] 

•  시작점 : 0, 중간점 : 2, 끝점 : 6 (소수점 이하는 제거) 으로 지정할 수 있습니다.
•  찾고자 하는 값보다 중간점의 위치의 값이 작다면 중간점부터 시작점까지의 데이터는 확인할 필요가 없습니다.
•  따라서, 중간점의 오른쪽 데이터로 시작점을 옮기고 다시 시작점, 중간점, 끝점을 정합니다.

[Step 3]

•  시작점 : 4, 중간점 : 4, 끝점 : 6 (소수점 이하 제거) 으로 지정할 수 있습니다.
•  이때, 중간점의 4는 우리가 찾고자 하는 값과 같기 때문에 여기에서 탐색을 마치게 됩니다.
•  우리가 찾고자 하는 값은 인덱스 [2]에 위치한다는 것을 알 수 있고, 이를 통해서 우리는 3번의 Step 만으로 탐색을 완료할 수 있게 되었습니다.

---

이진 탐색의 시간 복잡도

---

---

이진 탐색 소스코드 : 재귀 함수 구현 (python)

---

#이진 탐색 소스코드 구현 (재귀 함수)
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(찾고자 하는 값)을 입력 받기
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)

---

이진 탐색 소스코드 : 반복문 구현 (python)

---

#이진 탐색 소스코드 구현 (반복문)
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(찾고자 하는 값)을 입력 받기
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)

---

파이썬 이진 탐색 라이브러리

---

• binary_left(a, x) : 정렬된 순서를 유지하면서 배열 a에 x를 삽입할 가장 왼쪽 인덱스를 반환
• binary_right(a, x) : 정렬된 순서를 유지하면서 배열 a에 x를 삽입할 가장 오른쪽 인덱스를 반환

---

from bisect import bisect_left, bisect_right

a = [1, 2, 4, 4, 8]
x = 4

print(bisect_left(a, x))
print(bisect_right(a, x))

---

파라메트릭 서치(Parametric Search)

---

•  파라메트릭 서치란 최적화 문제를 결정 문제('Yes' or 'No')로 바꾸어 해결하는 기법입니다. 코딩 테스트에서 이 유형은 이진 탐색을 이용하여 해결할 수 있습니다.

---