[검색] 이진검색 알고리즘

1. 이진검색

정렬되어 있는 자료구조에서 중앙값과의 크고 작음을 이용해서 데이터를 검색한다.

(이진검색에서 주의할 점은 데이터가 꼭 정렬되어있어야 한다.)

 

[0] [1] [2] [3] [4] [5] [6] [7] [8]

 1   2   3   4   5   6   7   8   9

 

중앙값이 [4]므로 검색대상과 '5'를 비교한다.

검색대상이 '2'인 경우, 2<5 므로

 

[0] [1] [2] [3] [4]

 1   2   3   4   5

 

다시 중앙값이 [2] 3이므로 검색대상과 '3'을 비교한다. 이렇게 검색범위를 좁혀나가는 것.

2<3이므로 

 

[0] [1] [2]

 1   2   3

 

중앙값이 [1] 2이고 검색대상이 2므로

2=2로 원하는 대상 [1] 2를 찾을 수 있다.

 

따라서 초기화하는 변수는 startIdx, endIdx, midIdx, midVal가 되겠다.

 

그리고 if~elif~문으로 searchData가 midVal보다 큰 경우, 작은 경우, 같은 경우를 나눠준다.

코드는 아래와 같다.

 

# 정렬되어있는 자료구조
datas = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]
print(f'datas : {datas}')
print(f'datas length : {len(datas)}')

searchData = int(input('찾으려는 숫자 입력 : '))
searchResultIdx = -1

startIdx = 0
endIdx = len(datas) - 1
midIdx = (startIdx + endIdx) // 2
midVal = datas[midIdx]

#while searchData in datas지만 알고리즘에선 in을 쓸 수 없다. 고로 수식으로 나타내야함. 정렬되어있으므로 크다 작다로 datas에 들어있음을 확인가능
while searchData <= datas[len(datas)-1] and searchData >= datas[0]:
    # 끝에있는 숫자는 //2에 의해서 절대 midVal가 될 수 없으므로 따로 if문으로 빼내줘야한다
    if searchData == datas[len(datas)-1]:
        searchResultIdx = len(datas)-1
        break
    if searchData > midVal:
        startIdx = midIdx
        #endIdx는 그대로
    elif searchData < midVal:
        endIdx = midIdx
        #startIdx는 그대로
    elif searchData == midVal:
        searchResultIdx = midIdx
        break


    midIdx = (startIdx + endIdx) // 2
    midVal = datas[midIdx]
    
print(f'searchResultIdx : {searchResultIdx}')