이진 탐색(Binary Search)

정렬되어 있는 데이터에서 특정 데이터가 존재하는지 확인하는 알고리즘입니다.

 

[아이디어]

1. 데이터의 중간 인덱스에 해당하는 값과 찾고자 하는 값을 비교합니다.
2. 중간 인덱스의 값과 찾는 값이 일치하면 데이터가 존재하는 것입니다.
3. 찾고자 하는 값이 중간 인덱스의 값보다 작은 경우는 탐색 범위를 시작인덱스 ~ 중간인덱스 - 1 로 좁혀 다시 탐색을 진행합니다.
4. 찾고자 하는 값이 중간 인덱스의 값보다 큰 경우는 탐색 범위를 중간인덱스 + 1 ~ 끝인덱스로 좁혀 다시 탐색을 진행합니다.
5. 탐색 범위가 인덱스 하나로 좁혀졌으나 해당 인덱스의 값이 찾는 값과 다른 경우는 전체 데이터에서 찾는 값이 없다는 것을 의미합니다. 탐색할 인덱스가 하나 밖에 없는 상태에서 찾는 데이터가 hit하지 않으면 중간 인덱스의 값은 찾고자 하는 값보다 크거나 작게 되므로 시작 인덱스와 끝 인덱스의 값이 교차하게 되어 데이터를 찾지 못한 상태에서 이진탐색 반복문을 종료하게 됩니다.

 

[특징]

1. 이진 탐색을 위해서는 우선 데이터가 정렬되어 있어야 합니다.
2. 이진 탐색의 시간 복잡도는 O(logN)입니다.

 

[구현]

1. 반복문을 사용하여 구현

sv = input()
data_list = ['apple', 'banana', 'coconut', 'eggplant', 'fig', 'graph', 'kiwi', 'lemon', 'melon', 'orange', 'pear']


def binary_search(data, search_value):
    # 시작인덱스와 끝인덱스를 설정합니다.
    s = 0
    e = len(data) - 1
	
    # 시작인덱스가 끝인덱스보다 작거나 같을 동안 이진탐색을 진행합니다.
    # 시작인덱스와 끝인덱스가 교차하게 되면 더 이상 탐색할 요소가 없음을 뜻하기 때문에 반복문을 종료합니다.
	while s <= e:
        # python에서는 정수의 overflow를 신경쓸 필요가 없어 중간인덱스를 구할 때
        # m = (s + e) // 2 으로 표현해도 됩니다. 다만 java 등의 언어와 같이 정수 overflow에
        # 주의해야 하는 언어의 경우는 아래와 같이 중간인덱스를 구해야 합니다.
        m = (e - s) // 2 + s
        
        # 중간인덱스의 값이 찾는 값과 동일하다면 해당 인덱스를 반환합니다.
        if data[m] == search_value:
            return m
        # 찾고자 하는 값이 중간인덱스의 값 미만이면, 중간인덱스 이상의 데이터는 더 이상 탐색하지 않습니다.
        elif data[m] > search_value:
            e = m - 1
        # 찾고자 하는 값이 중간인덱스의 값을 초과하면, 중간인덱스 이하의 데이터는 더 이상 탐색하지 않습니다.
        else:
            s = m + 1
    # 값을 찾지 못하면 None을 리턴합니다.
    return None


print(binary_search(data_list, sv))

 

2. 재귀호출을 사용하여 구현

def binary_search(data, start_index, end_index, search_value):
    middle_index = (start_index + end_index) // 2
    if start_index > end_index or middle_index > len(data) - 1:
        return None
    if data[middle_index] == search_value:
        return middle_index
    elif data[middle_index] > search_value:
        return binary_search(data, start_index, middle_index - 1, search_value)
    else:
        return binary_search(data, middle_index + 1, end_index, search_value)


data = [1, 3, 5, 7, 9]
while True:
    value = input()
    if value == 'q' or value == 'quit':
        break
    try:
        value = int(value)
    except ValueError:
        print("Input integer only\n If you want to quit, press q or quit")
        continue
    print(binary_search(data, 0, len(data), value))