[알고리즘] Binary Search

 

Binary Search

---

이진 탐색 알고리즘을 말 그대로 탐색 알고리즘이다. 하지만 단순하게 처음부터 마지막까지 순서대로 비교하면서 탐색하는 방법이 아닌, 탐색 범위를 좁혀가며 데이터를 찾아내는 방식이다. 이진 탐색 알고리즘을 적용하기 위한 조건으로 배열 혹은 리스트에 있는 데이터들은 정렬이 되어있어야 한다. 그리고 찾으려는 데이터와 중간점에 위치한 데이터를 반복적으로 비교하면서 원하는 데이터를 찾게 된다.

이진 탐색 알고리즘은 재귀호출을 이용하여 구현할 수도 있고, 반복문을 이용해서 구현할 수도 있다.

 

 

Example Code

---

def binary_search(source, target, start, end):
    if start > end:
        return None
    mid = (start + end) // 2
    
    if source[mid] == target:
        return mid
    elif source[mid] > target:
        return binary_search(source, target, start, mid - 1)
    else:
        return binary_search(source, target, mid + 1, end)
    
data_list = [1, 2, 3, 4, 5, 6, 7, 8, 9]
data_target = 4

result = binary_search(data_list, data_target, 0, len(data_list)-1)

if result:
    print(result+1)
else:
    print("None")

위 코드는 재귀호출을 이용하여 이진 탐색 알고리즘을 구현한 예시이다. 

 

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

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

    return None


data_list = [1, 2, 3, 4, 5, 6, 7, 8, 9]
data_target = 7

result = binary_search(data_list, data_target, 0, len(data_list)-1)
if result:
    print(result + 1)
else:
    print('None')

위 코드는 반복분을 이용하여 구현한 이진탐색 코드이다.

 

 

파이썬에서 이진탐색을 할 수 있게 리스트를 만들어주는 기능을 제공하고 있다.

from bisect import bisect_left, bisect_right
data_list = [1, 2, 3, 4, 5, 6]
data_input = 4

# 왼쪽부터 시작해서 삽입을 결정한다.
print(bisect_left(data_list, data_input))

# 오른쪽쪽부터 시작해서 삽입을 결정한다.
print(bisect_right(data_list, data_input))

bisect_left 함수는 왼쪽부터 시작해서 첫번째 파라미터로 받은 리스트에 두번째 파라미터로 받은 데이터를 삽입하는 과정이고, 삽입이 완료된 후에는 삽입된 자리의 인덱스 번호를 반환한다. bisect_right는 반대로 진행된다.

 

 

 

Reference

---

https://namu.wiki/w/%EC%9D%B4%EC%A7%84%20%ED%83%90%EC%83%89

https://velog.io/@kimdukbae/%EC%9D%B4%EB%B6%84-%ED%83%90%EC%83%89-%EC%9D%B4%EC%A7%84-%ED%83%90%EC%83%89-Binary-Search