[알고리즘] 이진탐색(Binary Search)

이진 탐색

- 컴퓨터과학, 수학등에서 오름차순으로 정렬된 정수의 리스트를 같은 크기의 두 부분 리스트로 나누고 필요한 부분에서만 탐색하도록 제한하여 원하는 원소를 찾는 알고리즘

리스트의 중간 부분에 찾는 원소가 있는지 확인하고, 없으면 위쪽에 있는지 아래쪽에 있는지 판단하여 맨 앞부터 검색하거나 중간부터 검색한다

 

 

이진탐색과 순차탐색

위의 이미지 출처 

Binary Vs Linear Search Through Animated Gifs

위에서 보면 순차탐색은 11번해봐야알 수 있는데 이진탐색은 3번 해보면 알 수 있기 때문에 이진탐색이 좋다는 것이다.

하지만 정렬이 되어 있다는 가정하에 해야 원하는 값을 구할 수 있다.

 

 

분할 정복 알고리즘 (Divide and Conquer)으로 코드를 만들어보자

def binary_search(data_list, search):
    if len(data_list) == 1 and search == data_list[0]:
        return True
    if len(data_list) == 1 and search != data_list[0]:
        return False
    if len(data_list) == 0:
        return False
    
    mid = len(data_list) // 2
    if search == data_list[mid]:
        return True
    else:
        if search > data_list[mid]:
            return binary_search(data_list[mid+1:], search)
        else:
            return binary_search(data_list[:mid], search)

def binary_search(search,start,end):
    if start>end:
        return False
    mid=(start+end)//2
    if data[mid]==search:
        return True
    else:
        if data[mid]>search:
            return binary_search(search,start,mid-1)
        else:
            return binary_search(search,mid+1,end)

시간복잡도

만약 n개의 리스트가 있다고 해보자

1.  데이터가 n개일때 한 번의 비교연산으로 데이터의 갯수를 절반으로 줄인다. 즉 n/2로 줄인다.
2.  또 원하는 데이터를 찾기 위해 비교연산을 하고 못찾으면 n/2로 줄여간다
3. 데이터를 계속 반으로 줄여가면서 데이터가 1개 남을 때 까지 비교연산을 해서 찾았다고 하면

데이터가 1개일 때까지 몇번의 비교연산이 이루어졌는가?

데이터갯수가 n인 것이 1개가 되기 위해서 나눈 횟수를 k번 이라고 하면 비교연산은 k번 이루어진것이다.

그리고 마지막에 있어서 데이터가 1개일 때에 해당하는 것은 k번에 포함시키지 않기에

시간복잡도는 k+1이다

 

여기에서 k에 대한 식을 구해보자

이런식으로 나타내어 지게 되는데 이것을 일반화해서 k가 결과가 되게 식을 만들어보자

 

위의 식이 만들어지는 결과이며

따라서 시간복잡도는

시간복잡도

가 나오게 된다.