Python 이진탐색 알고리즘

Python 이진탐색 알고리즘

 

1~100 사이에서 숫자 하나를 맞춰야 한다면 알고리즘의 관점에선 가장 효율적인 방법은 범위의 절반인 50을 시도해보는 것이다.

 

대답이 UP이라면 1~49는 후보에서 없어지고, 대답이 DOWN이라면 51~100이 후보에서 없어지기 때문이다.

 

이러한 방법을 이진탐색이라 한다.

 

finding_target = 14
finding_numbers = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16]

def is_existing_target_number_binary(target, array):
    current_min = 0
    current_max = len(array) -1
    current_guess = current_min + current_max // 2 # 소숫점은 필요없기 때문에
    find_count = 0

    while current_min <= current_max:
        find_count += 1
        if array[current_guess] == target:
            print(find_count)
            return True
        elif array[current_guess] < target:
            current_min = current_guess +1 #최솟값을 시도값 +1로 변경 / 다운은 최댓값을 시도값 -1로 변경
        else:
            current_max = current_guess -1

        current_guess = (current_max + current_min) // 2 # 새롭게 current_guess를 업데이트
    return False # 한번도 발견되지 않았다면 return False


result = is_existing_target_number_binary(finding_target, finding_numbers)
print(result)

16에서 14를 찾는다.

 

def is_existing_target_number_binary(target, array):
    current_min = 0
    current_max = len(array) -1
    current_guess = current_min + current_max // 2 # 소숫점은 필요없기 때문에
    find_count = 0

함수가 실행되면,

최소, 최대 값의 변수를 만든다. 최대값을 설정할 때는 array로 넘어온 자료가 리스트이기 때문에 0부터 시작하니 범위에서 1만큼 빼준다.

추측하는 값인 current_guess를 최대값 + 최소값 // 2로 변수를 만든다.

 

소숫점은 필요없기 떄문에 //를 사용한다.

 

find_count는 순차탐색과 비교하기 위해서 넣은 변수다.

 

    while current_min <= current_max:
        find_count += 1
        if array[current_guess] == target:
            print(find_count)
            return True
        elif array[current_guess] < target:
            current_min = current_guess +1 #최솟값을 시도값 +1로 변경 / 다운은 최댓값을 시도값 -1로 변경
        else:
            current_max = current_guess -1

        current_guess = (current_max + current_min) // 2 # 새롭게 current_guess를 업데이트
    return False # 한번도 발견되지 않았다면 return False

while문을 돌린다.

최소값이 최대값보다 작을 경우 계속해서 돌아간다. 어차피 최소값이 최대값보다 작거나 같아지기 전에 타겟넘버를 찾기 때문이다.

 

find_count 는 순차탐색과 비교하기 위해 넣은 연산자다.

 

 

만약 array의 current_guess 번 째 인덱스가 target과 같다면

바로 True를 반환해주고 함수를 끝낸다.

 

elif

만약 current_guess번째 인덱스가 target보다 작다면,

최소값 설정을 추측값에서 +1만큼 해준다.

 

ex) 1~16에서 14를 찾아야하는데. 처음엔 8이 나올 것.

그럼 최소값은 8에서 +1한 9값이 될 것이다. 어차피 8이 아니었으니까 +1해서 다시 9~16만큼의 이분탐색으로 들어가는 것이다.

 

else

다른 경우라면 current_guess번째 인덱스가 target보다 클 경우인데, 이때는 최대값을 추측값에서 -1만큼 빼준다.

 

ex) 1~16에서 5를 찾아야하는데, 8이 나왔을 경우는, 최소값은 그대로 두고 최대값만 7로 설정해서, 1~7사이에서 타겟넘버를 찾는 것이다.

 

if, elif, else문이 끝나면 current_guess 즉 추측값을 새로 설정된 최대값과 최소값을 더해 2로 나눈다.

그리고 다시 while문으로 돌아간다.

 

만약 이 과정에서 타겟넘버가 한 번도 발견되지 않았다면 False를 리턴한다.

 

---

순차탐색과의 비교

finding_target = 14
finding_numbers = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16]

# O(N)

def is_existing_target_number_sequential(target, array):
    find_count = 0
    for number in array:
        find_count +=1
        if target == number:
            print(find_count)
            return True

    return False


result = is_existing_target_number_sequential(finding_target, finding_numbers)
print(result)  # True

똑같이 1~16사이에 14를 찾는 과정인데,

14를 찾기 까지 총 14번의 fint_count가 확인되고

이분탐색은 14를 찾기까지 총 3번의 fint_count를 확인할 수 있다.

 

이분탐색이 좀 더 효율적인 것을 알 수 있다.