이분탐색(Binary Search)

이분탐색(=이진탐색)이란?

 

정렬되어 있는 배열에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법

 

• 이분 탐색은 배열 내부의 데이터가 정렬되어 있어야만 사용할 수 있는 알고리즘
• 정렬된 리스트에만 사용할 수 있다는 단점이 있지만, 검색이 반복될 때마다 검색 범위가 절반으로 줄기 때문에 속도가 빠르다는 장점 존재
• 변수 3개(start, end, mid)를 사용하여 탐색. 찾으려는 데이터와 중간점 위치(mid)에 있는 데이터를 반복적으로 비교해서 원하는 데이터를 찾는 것이 이진 탐색의 과정

 

 

 

 

 

 

 

 

 

 

 

 

이분탐색 과정

1. 배열의 중간 값(mid)을 가져옴

 

2. 중간 값과 찾으려는 데이터 값을 비교

 

3. 중간 값이 찾고자 하는 데이터와 같다면 종료 (mid = key)

   ▷ 중간 값보다 찾고자 하는 데이터 값이 크다면, 중간값 기준 배열의 오른쪽 구간을 대상으로 탐색 (mid < key)

   ▷ 중간 값보다 찾고자 하는 데이터 값이 작다면, 중간값 기준 배열의 왼쪽 구간을 대상으로 탐색 (mid > key)

 

4. 값을 찾을 때까지 반복

 

 

 

 

 

---

예시) 찾고자 하는 key 데이터 = 32

 

1) low, mid, high 값 설정

 

 

 

2) Mid < key 이므로, Mid값을 기준으로 오른쪽 구간을 탐색 범위로 설정

 

 

 

3) 변경된 low, high값에 기반해 Mid 값 다시 설정

 

 

 

4) 이번에는 Mid > key 이므로, Mid 값을 기준으로 왼쪽 구간을 탐색 범위로 설정

 

 

 

5) Mid 값 다시 설정

 

 

6) 찾고자 하는 값 (32)와 Mid 값이 동일하므로, 데이터를 반환

 

 

 

 

 

 

 

 

 

 

 

 

 

 

이분탐색 코드

 

1) 반복문 이용

def binary_search(array, target, start, end):
    while start <= end:
        mid = (start + end) // 2

        # 원하는 값 찾은 경우 인덱스 반환
        if array[mid] == target:
            return mid
        # 원하는 값이 중간점의 값보다 작은 경우 왼쪽 부분(절반의 왼쪽 부분) 확인
        elif array[mid] > target:
            end = mid - 1
        # 원하는 값이 중간점의 값보다 큰 경우 오른쪽 부분(절반의 오른쪽 부분) 확인
        else:
            start = mid + 1

 

 

 

 

 

2) 재귀함수 이용

def binary_search(array, target, start, end):
    if start > end:
        return None
    mid = (start + end) // 2

    # 원하는 값 찾은 경우 인덱스 반환
    if array[mid] == target:
        return mid
    # 원하는 값이 중간점의 값보다 작은 경우 왼쪽 부분(절반의 왼쪽 부분) 확인
    elif array[mid] > target:
        return binary_search(array, target, start, mid - 1)
    # 원하는 값이 중간점의 값보다 큰 경우 오른쪽 부분(절반의 오른쪽 부분) 확인
    else:
        return binary_search(array, target, mid + 1, end)

 

 

 

 

 

 

 

 

 

 

 

 

이분탐색 시간복잡도

O(logN)

단계마다 탐색 범위를 반으로 나누므로 위와 같은 시간 복잡도를 가짐

 

EX) 처음 데이터의 개수가 32개라면, 이론적으로 1단계를 거치면 약 16개의 데이터가 남고, 2단계에서 약 8개, 3단계에서 약 4개의 데이터만 남게 됨.
즉, 이분 탐색은 탐색 범위를 절반씩 줄이고, O(logN)의 시간 복잡도를 보장