[Algorithm/Python] 이진 탐색(Binary Search)란?

들어가며

본 포스팅에서는 순차 탐색(Sequential Search)과 이진 탐색(Binary Search)에 대해 소개합니다.

---

📌 순차 탐색이란?

순차 탐색(Sequential Search)이란, 특정 데이터를 찾기 위해 앞에서부터 차례대로 값을 비교해나가는 탐색 방식입니다.
 
1️⃣ 가장 첫 번째 데이터를, 찾고자하는 데이터(타겟)과 비교합니다.
2️⃣ 값이 서로 일치하지 않는다면, 다음 데이터로 이동하여 비교합니다.
3️⃣ 이를 반복하며 일치할 때, 탐색을 종료합니다.

 

✅[ CODE ]

def sequential_search(n, target, arr):
    for i in range(n):
        if arr[i] == target:
            return i + 1

i + 1 번째의 데이터가 타겟과 동일하다는 결과를 얻을 수 있다.

 

☑️ 시간 복잡도

데이터의 정렬 여부와는 상관없이 앞에서부터 차례대로 비교해 나가야 합니다. 따라서, 원소의 개수 N개 만큼의 비교 연산이 필요해지므로, 순차 탐색의 최악의 시간 복잡도는 $O(N)$입니다.

 

---

📌 이진 탐색이란?

이진 탐색(Binary Search)이란, 특정 데이터를 찾기 위해 탐색 범위를 절반씩 좁혀나가면 탐색하는 방식입니다.
리스트 내의 데이터가 정렬되어 있어야만 사용할 수 있다는 특징이 있습니다.
 
1️⃣ 탐색 범위의 시작점과 끝점을 통해 중간점을 구합니다. (소수점 이하 무시)
2️⃣ 찾고자 하는 데이터와 중간점을 비교합니다.
3️⃣ 중간점 < 타겟 데이터이라면, 시작점을 중간점의 다음 칸으로 옮깁니다.
4️⃣ 중간점 > 타겟 데이터이라면, 끝점을 중간점의 이전 칸으로 옮깁니다.
5️⃣ 중간점과 타겟 데이터가 일치하면, 탐색을 종료합니다.
 
아래의 예시와 함께 보자면,

이진 탐색 과정

1. 중간점인 11과 타겟 데이터인 7을 비교하면, 중간점이 더 큽니다. 따라서, 끝점을 중간점의 이전 칸으로 옮겨줍니다.
2. 다시 측정한 중간점인 4와 타겟 데이터인 7을 비교하면, 이번엔 중간점이 더 작습니다. 따라서, 시작점을 중간점의 다음 칸으로 옮겨줍니다.
3. 다시 측정한 중간점인 7과 타겟 데이터인 7을 비교하면, 일치하므로 탐색을 종료합니다.

 

☑️ 시간 복잡도

데이터의 범위가 절반씩 좁혀지기 때문에 연산 횟수는 $log_2(N)$에 비례하므로 시간 복잡도는 $O(logN)$입니다.
탐색하고자 하는 데이터의 개수가 1000만개 이상이거나, 탐색 범위의 크기가 1000억 이상인 경우, 이진 탐색을 활용하면 좋습니다.

 

✅[ CODE ] - 재귀함수 이용

def binary_search(start, end, arr, target):
    if start > end:
        return None
    
	  # 시작점과 끝점으로 중간점을 구한다.
    middle = (end + start) // 2

    # 타겟과 일치한다면, 탐색 종료
    if target == arr[middle]:
        return middle + 1    # 인덱스 + 1 번째 수라는 의미

    # 타겟과 비교하여, 시작점이나 끝점을 옮겨준다.
    if target < arr[middle]:
        end = middle - 1
    elif target > arr[middle]:
        start = middle + 1

    return binary_search(start, end, arr, target)

n, target = map(int, input().split())
arr = list(map(int, input().split()))

result = binary_search(0, n - 1, arr, target)
print(result)

재귀함수를 이용하여 반복적으로 범위를 좁혀나가며 구현된 방식입니다.

 

✅[ CODE ] - 반복문 이용

def binary_search(start, end, arr, target):
    # 시작점이 끝점보다 작거나 같을 동안에 실행
    while start <= end:
        middle = (end + start) // 2
        if target == arr[middle]:
            return middle + 1
        if target < arr[middle]:
            end = middle - 1
        else:
            start = middle + 1
    return None   

n, target = map(int, input().split())
arr = list(map(int, input().split()))

result = binary_search(0, n - 1, arr, target)
print(result)

반복문을 이용하여, 범위를 좁혀나가며 구현된 방식입니다.

 

---

포스팅 내용에 오류가 있는 경우, 댓글로 남겨주시면 감사드리겠습니다. 😃😃
힘내자아!

 

출처 ) 이것이 코딩 테스트다 with Python