이분 탐색 / 이진 탐색 (Binary Search)

• 이분 탐색은 배열을 반으로 나누어가며 검색 범위를 줄여나가는 방식으로 작동합니다. 시간 복잡도가 O(log n)으로, 배열이 커져도 검색 시간이 크게 증가하지 않기 때문에 매우 빠릅니다.
• 배열이 정렬이 되어있어야함 사용이 가능합니다.
• start, end, mid 세개의 변수를 활용하여 탐색 합니다.

이분 탐색의 원리

1. 초기 설정: 배열의 시작 인덱스와 끝 인덱스를 설정합니다. 예를 들어, 배열의 시작 인덱스는 0, 끝 인덱스는 배열의 길이 - 1입니다.

2. 중간 인덱스 계산: 배열의 중간 인덱스를 계산합니다. 중간 인덱스는 (시작 인덱스 + 끝 인덱스) / 2로 구할 수 있습니다. 정수 나눗셈을 사용해야 하므로 소수점 이하는 버려집니다.

3. 중간 값과 비교:

   • 중간 값이 찾고자 하는 값과 같으면: 검색을 종료하고 해당 인덱스를 반환합니다.
   • 중간 값이 찾고자 하는 값보다 작으면: 찾고자 하는 값이 중간 값의 오른쪽에 위치한다고 가정하고, 시작 인덱스를 중간 인덱스 + 1로 설정하여 오른쪽 부분 배열에서 검색을 계속합니다.
   • 중간 값이 찾고자 하는 값보다 크면: 찾고자 하는 값이 중간 값의 왼쪽에 위치한다고 가정하고, 끝 인덱스를 중간 인덱스 - 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  # 찾고자 하는 값이 배열에 없을 경우

# 예제 사용법
arr = [1, 3, 5, 7, 9, 11, 13, 15]
target = 7
index = binary_search(arr, target)
print(f"타겟 값 {target}의 인덱스는 {index}입니다.")

이 코드에서 binary_search 함수는 정렬된 배열 arr과 찾고자 하는 값 target을 인자로 받아, 값을 찾으면 인덱스를 반환하고, 찾지 못하면 -1을 반환합니다.

이분 탐색은 정렬된 데이터에만 사용할 수 있지만, 이 경우에는 매우 빠르고 효율적인 검색 방법이 됩니다.

[참고]

• https://velog.io/@kimdukbae/%EC%9D%B4%EB%B6%84-%ED%83%90%EC%83%89-%EC%9D%B4%EC%A7%84-%ED%83%90%EC%83%89-Binary-Search