Python - 이진검색

이진검색

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

정렬이 되어있는 자료구조에서 가운데 값과 찾는값을 비교하고

또 그 값에서 중간값을 찾는 방식으로 UpDown 게임과 유사한 방식이다.

 

이진검색 예제

datas = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]

print(f'data : {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 <= datas[len(datas) - 1] and searchData >= datas[0]:
    if searchData > midVal:
        startIdx = midIdx
        midIdx = (startIdx + endIdx) // 2
        midVal = datas[midIdx]
    elif searchData < midVal:
        endIdx = midIdx
        midIdx = (startIdx + endIdx) // 2
        midVal = datas[midIdx]
    elif searchData == midVal:
        searchResultIdx = midIdx
        break

if searchResultIdx == -1:
    print('찾는 값이 없습니다.')
else:
    print('찾는 값의 인덱스 : {}'.format(searchResultIdx))

내용

정렬이 되어있는 자료구조이기 때문에 첫번째 인덱스의 값과 마지막 인덱스 값을 비교하여 while문을 실행한다

가운데 값을 계속 비교하여 찾는값이 더 크면 시작 인덱스를 바꾸고

찾는값이 더 작으면 마지막 인덱스를 바꿔서 원하는 값의 인덱스를 찾는다.

 

결과

data : [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]
datas length : 11
찾으려는 수 입력 : 9
찾는 값의 인덱스 : 8

data : [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]
datas length : 11
찾으려는 수 입력 : 12
찾는 값이 없습니다.