이진탐색

 

# 이진탐색

class BinarySearch:
    def __init__(self, target):
        self.target = target

    def is_existing_target_number_binary(self, array: any) -> bool:
        len_array = len(array)
        min_index = 0
        max_index = len_array - 1
        start_index_num = (max_index + min_index) // 2

        while max_index >= min_index:
            # print(start_index_num)
            if array[start_index_num] == self.target:
                return True
            elif array[start_index_num] > self.target:
                max_index = start_index_num - 1
            else:
                min_index = start_index_num + 1
            start_index_num = (max_index + min_index) // 2

        return False

    def is_existing_target_number_sequential(self, array: any) -> bool:
        array.sort(reverse=True)
        for x in array:
            if x == self.target:
                return True
        return False

반드시 정렬이 되어있을때 사용가능 하다.

 

시간 복잡도

총 숫자가 1~N 까지라고 한다면, 1번 탐색하면 반절이 줄어드니 N/2 개가 남습니다. 2번 탐색하면 반절이 줄어드니 N/4 = N/2^2 개가 남습니다. 3번 탐색하면 반절이 줄어드니 N/8 = N/2^3 개가 남습니다. .... k번 탐색하면 반절이 줄어드니 N/2^k 개가 남습니다. 이 때, 이분탐색을 열심히 시도해서 딱 1개만 남았다고 가정을 해보겠습니다. 이걸 수식으로 표현하면, N/2^k = 1 입니다. 즉, k = log_2{N} 횟수를 시도하면 정답을 찾을 수 있습니다! 결론적으로 이분탐색을 위해서는 시간 복잡도가 O(logN) 만큼 걸린다. 라고 말할 수 있습니다. Q. 여기서 왜 log_2N 이 아니라 logN 인가요? A. 상수는 무시해도 되기 때문에 표기하기 쉽도록 logN 으로 부르기로 약속!

순차탐색의 경우와 이진탐색의 경우 차이

37을 찾을 때 걸린 스텝차이

 

'''
이진 탐색 과 일반탐색 시간 비교
'''
import time
now = time.time()
finding_numbers = list(range(100000000))

finding_numbers.sort()

binary_search = BinarySearch(2)
end = time.time()
print("리스트 생성시간 : ",end-now)
print("지금 : ",time.time())
now = time.time()
result = binary_search.is_existing_target_number_binary(finding_numbers)
end = time.time()
print("이진탐색 풀이 시간 : ",end-now)
print("지금 : ",time.time())
now = time.time()
result_2 = binary_search.is_existing_target_number_sequential(finding_numbers)
end = time.time()
print("순차탐색 풀이 시간",end-now)
print("지금 : ",time.time())
print(result,"vs",result_2)