[알고리즘] 이진탐색

[binary search]

• 정렬되어 있는 자료구조에서 중앙값의 크고 작음을 이용해서 데이터를 검색한다.
• 정렬되어 있지 않은 자료구조라면 먼저 정렬을 시켜 주어야 이진 탐색이 가능하다.
• 중앙값을 기준으로 검색 범위를 점차 좁혀나가는 방식이다.

---

다음과 같은 자료구조가 있다고 하자.

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

이때 중앙값은 5 이다.

우리가 찾으려는 값을 2라고 한다면, 5보다 큰 값을 굳이 검색할 필요는 없을 것이다.

 

[ 1, 2, 3, 4, 5 ]

여기서의 중앙값은 3이다.

따라서 4, 5는 필요가 없으므로 버려지게 된다.

 

[ 1, 2, 3 ]

중앙값은 2 이다.

바로 내가 찾으려는 값이다.

---

 

• 반복문을 사용한 이진탐색 예시

코드 참조; 나동빈 (2020). <이것이 취업을 위한 코딩 테스트다 with 파이썬>. 서울시: 한빛미디어.

def binary_search(array,target,start,end):
    while start<= end:
        mid = (start + end)//2
        if array[mid] == target :
            print(f'mid : {array[mid]}')
            return mid
        elif array[mid] < target :
            start = mid+1
            print(f'mid : {array[mid]}')
        else :
            end = mid - 1
            print(f'mid : {array[mid]}')
    return None

array = [1,2,3,4,5,6,7,8,9,10,11]
print(f'array : {array}')
target = int(input('찾을 데이터는 : '))
print(f'데이터는 {binary_search(array,target,0,len(array))}번 인덱스에 있습니다.')

'''
array : [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]
찾을 데이터는 : 0
mid : 6
mid : 3
mid : 1
데이터는 None번 인덱스에 있습니다.

array : [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]
찾을 데이터는 : 11
mid : 6
mid : 9
mid : 11

array : [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]
찾을 데이터는 : 3
mid : 6
mid : 3
데이터는 2번 인덱스에 있습니다.
'''