이진 탐색 (Binary Search)

이진 탐색

: 데이터가 정렬되어 있는 배열에서 특정한 값을 찾아내는 알고리즘이다. 반으로 쪼개가면서 탐색을 하는데 내부의 데이터가 반드시 정렬되어있어야 함.

배열의 중간에 있는 임의의 값을 선택하여 찾고자 하는 값 x와 비교한다. x가 중간 값보다 작으면 중간 값을 기준으로 좌측의 데이터들을 대상으로 비교하고, 크다면 배열의 우측을 대상으로 다시 탐색한다. 

-> 해당 값을 찾을 때까지 중간 값을 임의로 선택하고 비교하는 과정을 반복함.

 

 

예시)

my_list = [1, 9, 3, 5, 7, 13, 11, 17, 15] 라는 배열이 있음.

반드시 정렬 과정이 필요!

1 3 5 7 9 11 13 15 17 중에서 5를 찾고자 한다면

 

1 3 5 7 9 11 13 15 17 

처음값 1, 끝값 17 일때, 중간값은 9.

1 3 5 7 9 11 13 15 17

찾으려는 데이터 5가 9보다 작으므로 11부터 17까지의 데이터는 더이상 볼 필요가 없다.

1 3 5 7

끝 값을 9의 하나 앞인 7로하면 처음값은 1, 끝값은 7, 중간값은 3이다.

찾으려는 데이터 5가 3보다 크므로 1부터 3까지의 데이터는 볼 필요가 없다.

5 7

처음 값을 1의 하나 뒤인 5로 해주면 처음값은 5, 끝값은 7, 중간값은 5이다.

중간점에 위치한 데이터 5는 찾으려는 값과 동일하므로 탐색을 종료한다!

 

"중간값 = 찾으려는 데이터의 값"

 

 

---

 

파이썬으로 구현한 이진탐색 알고리즘

# 리스트 data, 찾는 값 target

def binary_search(data, target):
    start = 0
    end = len(data) - 1

    while start <= end:		# 탐색할 범위가 남아 있는 동안 반복
        mid = (start + end) // 2
        if target == data[mid]:	# 발견!
            return mid
        elif target < data[mid]:	# 찾는 값이 더 작으면 왼쪽으로 범위를 좁히기
            end = mid - 1
        else:		#찾는 값이 더 크면 오른쪽으로 범위를 좁히기
            start = mid + 1	
    return -1	# 찾지 못했을 때

my_list = [1, 9, 3, 5, 7, 13, 11, 17, 15]
my_list.sort()	# 반드시 정렬해주는 과정이 필요함
print(binary_search(my_list, 5))	# 리스트 data = my_list, 찾는 값 target = 5