Binary Search, 이진 탐색

이진탐색은 정렬된 배열 안에서 타깃 값의 인덱스를 찾는 탐색 알고리즘이다.

이진탐색은 배열의 중간 인덱스의 값을 타깃 값과 비교해 타깃 값의 인덱스를 찾는다.

 

 

 

 

 

 

 

 

 1. 문제 상황 

배열

문제 상황을 가정해 보자. 우리는 숫자 X가 위의 배열에 존재하는지 살펴볼 것이다.

 

⓵ X = 21 , 3번 인덱스에 존재

⓶ X = 25 , 존재하지 않음

⓷ X = 81 , 7번 인덱스에 존재

 

위의 상황을 해결하는 가장 간단한 방법은 배열을 전부 스캔해 X 값을 찾는 것이다.

0번 인덱스로부터 시작해, 타깃 값을 찾으면 인덱스 반환 및 종료를 하면 된다. 다만, 존재하지 않는 것을 알기 위해서는 8번 인덱스까지 스캔해야만 한다. 이 탐색 법은 최악의 경우, 배열의 사이즈만큼의 시간 복잡도가 필요하다.

 

다행히도, 이 상황을 선형 시간 복잡도로 해결할 수 있는 방법이 있다.

바로 0번 인덱스부터 스캔하는 것이 아닌, 중간 인덱스부터 스캔하는 것이다. 다만, 정렬된 리스트에서만 가능한 방법이다.

 

[Case 1] X 가 중간 인덱스의 값이랑 같은지 확인한다. 만약, 같다면 찾았다.

[Case 2] X 가 중간 인덱스의 값보다 작다면, ( 중간 인덱스 - 마지막 인덱스 ) 사이의 요소들은 버려도 된다. 👉🏻  탐색 범위가 반이 줄었다.

[Case 3] X 가 중간 인덱스의 값보다 크다면, ( 0번 인덱스 - 중간 인덱스 ) 사이의 요소들은 버려도 된다. 👉🏻  탐색 범위가 반이나 줄었다.

 

정렬된 리스트

 

위 배열에서 인덱스는 0부터 8까지 있으므로, 중간 인덱스는 4이다. X = 13이라고 가정해보자.

[1] X는 중간 인덱스의 값보다 작은가? YES [범위가 반으로 줄었다] 👉🏻 만약 있어도 [2,6,13,21] 사이에 있을 것임

[2] 중간 인덱스는 6 또는 13이 될 수 있다. ( (0+3)/2 = 1.5 ) 이므로 👉🏻 ceil 하거나 floor 해서 아무거나 하면 된다.

[3] floor 선택 👉🏻 중간 인덱스는 13가 된다.

[4] X는 중간 인덱스 값과 같은가? YES

 

위 방법은 스캔할 때마다 탐색 범위를 반으로 줄여준다. 

 

 

 

 

 

 

 

 

 

 

 2. 코드 구현  코드는 반복문과 재귀문으로 구현할 수 있다.

> 반복문

 

import math

def binarySearch(arr, target):
    arr.sort()
    start = 0
    end = len(arr) - 1
    
    while True:
        middle = math.floor((start + end) / 2)
        if start > end: return -1
        if target == arr[middle]: return middle
        elif target < arr[middle: end =  middle - 1
        elif target > arr[middle]: start = middle + 1
        
arr = [36, 47, 2, 13, 6, 81, 97, 21, 63]
print(binarySearch(arr, 25)) # -1
print(binarySearch(arr, 13)) # 2

 

 

 

> 재귀문

 

import math

arr = [36, 47, 2, 13, 6, 81, 97, 21, 63]
arr.sort()

def binarySearch(start, end, target):
    if start > end: return -1
    
    middle = math.floor((start + end) / 2)
    
    if target == arr[middle]: return middle
    elif target < arr[middle]: 
    	return binarySearch(start, middle-1, target)
    elif target > arr[middle]: 
    	return binarySearch(middle+1, end, target)
    
print(binarySearch(0, len(arr)-1, 13))

 

 

 

 

 

 

 

 

 3. 알고리즘 성능 

이진 탐색의 최악의 경우 시간 복잡도는 log(n)이다. ( n을 계속 반으로 나누기 때문에 )

 

 

 

👇🏻 한번 풀어보는 것도 좋을...듯

https://www.acmicpc.net/problem/10815

10815번: 숫자 카드