Binary Search란

Binary Search(이분 탐색, 이진 탐색)이란

- 데이터가 정렬되어 있는(binary search의 주요 조건) 배열에서 특정 값을 찾아내는 알고리즘

- 배열의 중간에 있는 임의의 값을 선택해서, 찾고자 하는 값 X와 비교한다

- X가 중간값보다 작으면 중간값을 기준으로 왼쪽의 데이터를 대상으로,

- X가 중간값보다 크면 배열의 우측을 대상으로 다시 탐색한다

- 동일한 과정을 해당 값을 찾을 때까지 반복한다

 

예시

array =[1, 2, 3, 4, 5, 6] 에서 6을 찾자

 

step 1

중간값 middle = 3

3과 6을 비교한다 -> 3 < 6

 

step 2

3의 오른쪽에 있는 리스트 [4, 5, 6]에서 탐색한다

 

중간값 middle = 5

5와 6을 비교한다 -> 5 < 6

 

step 3

5의 오른쪽에 있는 리스트 [6]을 탐색한다

6 == 6이므로 탐색을 종료한다

 

코드 구현

- 반복문

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

 

- 재귀

BsearchRecursive(array, target, low, high):
    if low > high:
        return -1
    
    mid = (low + high) // 2
    
    if array[mid] == target:
        return mid
    elif array[mid] > target:
        return BsearchRecursive(array, target, low, mid - 1)
    else:
        return BsearchRecursive(array, target, mid + 1, high)

 

시간 복잡도

O(log n)

 

 

- 출처: 이진 탐색(Binary Search) 알고리즘 개념 이해 및 추가 예제, [알고리즘] 이분 탐색(Binaray Search)