이진 검색

Python SELF KO

레벨 53 , 레슨 1

사용 가능

2.1 이진 검색의 정의와 주요 개념

이진 검색 — 정렬된 배열에서 요소를 찾는 알고리즘으로, 배열을 절반으로 나누는 원리로 작동해. 이 알고리즘은 큰 배열에 대한 선형 검색보다 훨씬 효율적이야, 왜냐면 각 반복마다 배열을 두 부분으로 나누어 검사를 줄이거든.

주요 개념들:

정렬된 배열: 이진 검색은 정렬된 배열에서만 작동해.
절반으로 나누기: 알고리즘은 중간의 요소와 찾고자 하는 요소를 비교해.
재귀적 또는 반복적 나누기: 찾고자 하는 요소가 중간 요소보다 작으면 왼쪽 절반에서 검색을 계속하고, 크면 오른쪽 절반에서 계속해.
종료 조건: 요소가 발견되거나 검색 범위가 비어질 때 검색을 중단해.

중요! 이진 검색을 위해서는 정렬된 배열이 필요해.

이진 검색이 제대로 작동하려면 입력 데이터가 오름차순으로 정렬되어 있어야 해. 이는 알고리즘이 배열의 요소들이 정렬되어 있다는 사실에 의존하기 때문이야. 덕분에 각 검색 단계에서 절반의 요소들을 효과적으로 제외할 수 있어.

정렬된 배열의 예:


sorted_array = [1, 3, 5, 7, 9, 11, 13]

2.2 이진 검색의 단계별 구현

이진 검색의 작동 원리:

초기화: 검색의 초기 경계를 설정 (배열의 왼쪽과 오른쪽 경계).
중간 요소 선택: 배열의 중간 요소의 인덱스를 찾아.
비교: 중간 요소와 찾고자 하는 값을 비교해.
경계 업데이트:
1. 중간 요소가 찾고자 하는 값과 같다면, 해당 인덱스를 반환해.
2. 찾고자 하는 값이 중간 요소보다 작다면, 오른쪽 경계를 업데이트해.
3. 만약 크다면 — 왼쪽 경계를 업데이트해.
반복: 요소가 발견되거나 왼쪽 경계가 오른쪽 경계보다 커질 때까지 2-4단계를 반복해.

단계별 알고리즘:

초기화: left를 0으로 그리고 right를 len(arr) - 1로 설정해.
중간 요소 계산: mid = (left + right) // 2
목표 요소와 비교:
1. 만약 arr[mid] == target이라면, mid를 반환해.
2. 만약 arr[mid] < target이라면, left = mid + 1로 업데이트해.
3. 만약 arr[mid] > target이라면, right = mid - 1로 업데이트해.
반복: left <= right일 때까지 2단계로 돌아가.
요소가 발견되지 않으면: -1을 반환해.

Python에서 이진 검색의 반복적 구현:


def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

# 사용 예제:
sorted_array = [1, 3, 5, 7, 9, 11, 13]
target = 7
result = binary_search(sorted_array, target)
print(f"요소 {target}은(는) 인덱스 {result}에서 발견되었어")  # 출력: 요소 7은(는) 인덱스 3에서 발견되었어

2.3 이진 검색의 시간 복잡도 `O(log n)`

이진 검색은 O(log n)의 시간 복잡도를 가지고 있어, 여기서 n은 배열의 요소 수야. 이는 알고리즘이 각 단계에서 요소 수를 절반으로 나누어, 선형 검색의 O(n) 시간 복잡도에 비해 검색을 상당히 빠르게 해준다는 걸 의미해.

시간 복잡도 분석:

최상의 경우 (Best case): 첫 단계에서 요소가 발견됨, O(1).
평균 경우 (Average case): O(log n).
최악의 경우 (Worst case): 마지막 단계에서 요소가 발견되거나 없을 경우, O(log n).

시간 복잡도 분석 예제:


sorted_array = [1, 3, 5, 7, 9, 11, 13]
target = 7
index = binary_search(sorted_array, target)
print(f"요소 {target}은(는) 인덱스 {index}에서 발견되었어")  # 출력: 요소 7은(는) 인덱스 3에서 발견되었어

# 알고리즘은 요소를 찾기 위해 3단계 (7 요소의 로그)를 수행, 
# 이는 O(log n)에 해당해

복잡도의 그래픽 표현:

16개의 요소가 있는 배열을 상상해봐.