이진 탐색

: 배열을 반으로 나누어 검색 범위를 좁혀가며 탐색하는 알고리즘

• 조건: 오름차순으로 정렬된 상태에서 시작해야 한다.
• 시간 복잡도: O(longN)

진행 과정

1. 자료를 오름차순으로 정렬한다.
2. 자료의 중간값(mid)이 찾고자 하는 값(target)인지 비교한다.
3. mid 값이 target과 다르다면 대소 관계를 비교하여 탐색 범위를 좁히고, target과 mid 값이 같을 때까지 아래 조건에 따라 2번과 3번을 반복한다.
   1. target이 mid 값보다 작으면 end를 mid 왼쪽 값으로 바꿔준다. (절반의 왼쪽 탐색)
   2. target이 mid 값보다 크면 start를 mid 오른쪽 값으로 바꿔준다. (절반의 오른쪽 탐색)

예시) { 17, 28, 43, 67, 88, 92, 100 }, 43 찾기

• 가운데에 위치한 임의의 값 선택: 67

  → 선택한 값(67)과 찾고자 하는 값(43) 비교: 43 < 67

  → 43은 67의 왼쪽에 존재함

• 67을 기준으로 왼쪽에 있는 배열 값들을 대상으로 다시 탐색 진행

  { 17, 28, 43 }

  → 가운데의 임의의 값 선택: 28

  → 선택한 값(28)과 찾고자 하는 값(43) 비교: 28 < 43

  → 43은 28의 오른쪽에 존재함

• 28의 오른쪽을 기준으로 배열을 다시 설정해보면

  { 43 }

  → 배열에 값이 하나만 남게 되고, 값을 확인해 보면 원하는 값을 찾았다!

반복문을 활용한 이진 탐색 구현

def binary_search_iterative(arr, target):
    start = 0
    end = len(arr) - 1

    while start <= end:
        mid = (start + end) // 2

        if arr[mid] == target:
            return mid  # 탐색 성공 시 인덱스 반환
        elif arr[mid] > target:
            end = mid - 1  # 중간 값보다 작은 경우 왼쪽 탐색
        else:
            start = mid + 1  # 중간 값보다 큰 경우 오른쪽 탐색

    return -1  # 탐색 실패 시 -1 반환

# 테스트 코드 
arr = [2, 4, 7, 10, 13, 18, 21]
target = 10
result = binary_search_iterative(arr, target)
if result == -1:
    print("탐색 실패")
else:
    print("탐색 성공, 인덱스:", result)

재귀 함수를 활용한 이진 탐색 구현