lesson1Title

lesson2Title

lesson3Title

lesson4Title

lesson5Title

lesson6Title

pythonIntroAlgorithms1Chapter3Title

lesson7Title

lesson8Title

lesson9Title

lesson10Title

lesson11Title

lesson12Title

lesson13Title

lesson14Title

lesson15Title

lesson16Title

lesson17Title

lesson18Title

lesson19Title

pythonIntroAlgorithms1Chapter1Title

pythonIntroAlgorithms1Chapter2Title

pythonIntroAlgorithms1Chapter4Title

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

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

        if arr[mid] == target: # 찾은 경우 중간점 인덱스 반환
            return mid
        elif arr[mid] < target: # 중간점의 값보다 찾고자 하는 값이 큰 경우 오른쪽 확인
            start = mid + 1
        else: # 중간점의 값보다 찾고자 하는 값이 작은 경우 왼쪽 확인
            end = mid - 1

    return -1  # 찾지 못한 경우


# 예시
arr = [1, 3, 5, 7, 9, 11, 13, 15]

target = 7

result = binary_search(arr, target)

print(result)

# 이진 탐색 자세히 살펴보기

## 1. 초기 범위 설정

검색 범위의 시작점과 끝점을 설정합니다.

```python title="초기 범위 설정"
def binary_search(arr, target):
    start, end = 0, len(arr) - 1
```

<br />

## 2. 반복적인 비교 및 범위 조정

중간 요소를 확인하고, 검색 범위를 반으로 줄입니다.

```python title="반복적인 비교 및 범위 조정"
while start <= end:
    mid = (start + end) // 2 # 중간점
    if arr[mid] == target: # 찾은 경우
        return mid
    elif arr[mid] < target: # 중간점의 값보다 찾고자 하는 값이 큰 경우
        start = mid + 1
    else: # 중간점의 값보다 찾고자 하는 값이 작은 경우
        end = mid - 1

return -1  # 찾지 못한 경우
```

<br />

## 시간 복잡도

1. `최악의 경우 시간 복잡도`: O(log n)

   - 이진 탐색에서는 각 단계마다 검색 범위를 반으로 줄입니다. 따라서, n개의 요소가 있을 때, 최대 log n번의 단계를 거쳐야 합니다.

2. `최선의 경우 시간 복잡도`: O(1)

   - 찾고자 하는 요소가 중간점에 위치하는 경우, 첫 번째 비교에서 바로 찾을 수 있습니다.

3. `평균 시간 복잡도`: O(log n)

   - 대부분의 경우, 이진 탐색은 로그 시간 복잡도를 가집니다. 이는 검색 과정에서 검색 범위가 매 단계마다 반으로 줄기 때문입니다.