이진 탐색 (Binary Search)

이진 탐색(Binary Search)은 효율적인 탐색 알고리즘으로, 정렬된 리스트에서 특정 값을 찾기 위해 사용된다. 이진 탐색은 리스트를 반으로 나누어 탐색 범위를 좁혀가는 방식으로 동작하며, 시간 복잡도가 O(log n)으로 매우 효율적이다.

설명 및 개념

이진 탐색은 다음과 같은 단계를 따른다:

1. 초기화: 리스트의 시작 인덱스와 끝 인덱스를 설정한다.
2. 중간 요소 계산: 시작 인덱스와 끝 인덱스의 중간 요소를 계산한다.
3. 비교:
   • 중간 요소가 찾고자 하는 값과 일치하면, 해당 요소의 인덱스를 반환한다.
   • 중간 요소가 찾고자 하는 값보다 크면, 끝 인덱스를 중간 인덱스의 왼쪽으로 이동시켜 리스트의 왼쪽 절반을 탐색한다.
   • 중간 요소가 찾고자 하는 값보다 작으면, 시작 인덱스를 중간 인덱스의 오른쪽으로 이동시켜 리스트의 오른쪽 절반을 탐색한다.
4. 반복: 이 과정을 찾고자 하는 값을 찾거나, 탐색 범위가 더 이상 존재하지 않을 때까지 반복한다.
5. 결과 반환: 리스트의 모든 요소를 검사한 후에도 찾고자 하는 값이 없으면, -1을 반환하여 값을 찾을 수 없음을 알린다.

시간 복잡도

이진 탐색의 시간 복잡도는 다음과 같다:

• 최선의 경우 (Best Case): O(1)
  • 찾고자 하는 값이 리스트의 중간 요소인 경우.
• 평균 경우 (Average Case): O(log n)
  • 리스트를 절반으로 나누어 탐색하기 때문에.
• 최악의 경우 (Worst Case): O(log n)
  • 리스트의 모든 절반을 탐색해야 하는 경우.

공간 복잡도

이진 탐색의 공간 복잡도는 O(1)이다. 이는 이진 탐색이 추가적인 메모리를 거의 사용하지 않기 때문이다. 단, 재귀적으로 구현할 경우 함수 호출 스택에 의해 O(log n)의 공간 복잡도를 가질 수 있다.

def binary_search(arr, target):
    left, right = 0, len(arr) - 1

    while left <= right:
        mid = left + (right - left) // 2

        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1

    return -1

arr = [2, 3, 4, 10, 40]
target = 10
result = binary_search(arr, target)
print(f"Element found at index: {result}")  # Output: Element found at index: 3

 

모든 코드는 github에 저장되어 있습니다.

https://github.com/SeongUk18/Algorithm/tree/main/Data_structure_algorithms