바이너리 서치 - Binary Search

처음 프로그래밍을 접하다 보면 여러 가지 알고리즘을 접하게 된다.

그중에 제일 먼저 배우게 되는 것이 데이터 처리 과정에서 많이 쓰이는 바이너리 서치(Binary Search)이다.

그렇다면 바이너리 서치란 무엇인가?

바이너리 서치 (Binary Search)

바이너리 서치는 주어진 배열에서 원하는 값을 빠르게 찾는 알고리즘으로,

이진 검색이라고도 불리며,

탐색 속도가 매우 빠르기 때문에 많이 활용된다.

 

바이너리 서치의 동작 방식

1. 탐색하고자 하는 배열의 가운데 값을 선택
2. 선택한 값과 찾고자 하는 값을 비교
3. 선택한 값이 찾고자 하는 값과 같다면, 탐색을 종료하고 값을 반환
4. 선택한 값이 찾고자 하는 값보다 크다면, 선택한 값의 왼쪽 부분 배열에서 1 ~ 3 단계를 반복
5. 선택한 값이 찾고자 하는 값보다 작다면, 선택한 값의 오른쪽 부분 배열에서 1 ~ 3 단계를 반복

이와 같은 방식으로 반복하면서 탐색 범위를 반으로 줄여가면서 원하는 값을 찾아낼 수 있다.

 

바이너리 서치의 장점은 배열의 크기가 매우 크거나 탐색이 반복적으로 이루어져야 할 경우,

탐색 속도가 매우 빠르다는 점.

 

또한, 배열이 정렬되어 있어야 한다는 제약이 있지만,

정렬되어 있다면 최악의 경우에도 O(log n)의 시간 복잡도를 가지기 때문에

다른 탐색 알고리즘보다 빠르게 동작한다.

 

그렇다면 파이썬으로 예를 보자.

참고로 파이썬에서는 bisect_left()함수를 쓰고 더 쉽게 찾을 수 있지만, 이 예제에서는 bisect_left() 함수를 사용하지 않았다.

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

arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
target = 7

result = binary_search(arr, target)

if result != -1:
    print(f"Value {target} is present at index {result}")
else:
    print(f"Value {target} is not present in the list")