[python] (알고리즘) binarySearch (이진탐색) 구현

binarySearch (이진탐색) 구현

코드

#이진탐색
data = [2, 11, 19, 27, 30, 31, 45, 121]
n = int(input('검색할 데이터를 입력하세요: '))

l = 0   #검색할 데이터 리스트의 첫번째 인덱스
h = len(data)-1   #검색할 데이터 리스트의 마지막 인덱스
count = 0   #검색 비교 횟수
isFlag = False   #데이터 검색의 성공 여부

while(l <= h):
    m = (l+h) // 2  # 중간 위치를 계산

    if n in data:
        if n == data[m]:    #검색비교완료
            isFlag = True
            break
        elif n > data[m]:
            l = m + 1
        elif n < data[m]:
            h = m - 1
    #count 위치 유의
    count += 1  # 비교횟수를 증가

print("{} 번 비교했습니다".format(count))

if isFlag:
    print("검색 완료!, 입력된 데이터 {}의 인덱스는 {} 입니다.".format(n, m))
else:
    print("검색 실패, 입력된 데이터 {}는 리스트에 존재하지 않습니다.")

실행결과

검색할 데이터를 입력하세요: 30
2 번 비교했습니다
검색 완료!, 입력된 데이터 30의 인덱스는 4 입니다.

count 의 위치에 따라 비교횟수가 달라지는 점 유의

while 문 끝에 비교 한 회차를 완료했을 때, count의 횟수 증가