자료구조 - 이진탐색

순차탐색

- 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서 부터 데이터를 하나씩 차례대로 확인하는 방법

순차탐색

- 최적의 시간복잡도 O(1) : 가장 첫번째에 찾고자 하는 데이터가 있는경우

- 최악의 시간복잡도 O(n) : 가장 마지막에 찾고자 하는 데이터가 있는경우

 

 

이진탐색

- 찾으려는 데이터와 정렬 된 리스트의 중간지점을 계속해서 재귀적으로 반복하며 비교해서 찾아내는 방법

- 데이터들이 정렬 되어 있어야 한다.

- 탐색하고자 하는 범위의 시작점, 끝점, 중간점의 변수를 사용한다.

 

34의 인덱스를 찾는다고 해보자

1. low ,middle, high = index : 0, 7, 15 설정, index(middle) < 34 이므로

2. low, middle, high = index : 8, 11, 15 설정, index(middle) > 34 이므로

3. low, middle, high = index : 8, 9, 10 설정, index(middle) < 34 이므로

4. low, middle, high = index : 10, 10, 10 설정, index(middle) = 34 이므로

 

34의 인덱스는 10이다.

 

이를 파이썬으로 구현해보자.

li = [2, 6, 11, 13, 18, 20, 22, 27, 29, 30, 34, 38, 41, 42, 45, 47]

def binary_search(arr, var, low, high):
    middle = int((low + high) / 2)
    if var == arr[middle]:
        return middle
    elif var < arr[middle]:
        # 재귀함수는 맨끝에 있는 것을 반환해야 맨 앞의 재귀함수까지 반환된다.
        return binary_search(arr, var, low, middle - 1)
    elif var > arr[middle]:
        return binary_search(arr, var, middle + 1, high)
    else:
        print("Cant search value")

print(binary_search(li, 22, 0, len(li) - 1))

위와 같이 재귀함수로 구현이 가능하다. 반복문으로도 구현이가능하다.

li = [2, 6, 11, 13, 18, 20, 22, 27, 29, 30, 34, 38, 41, 42, 45, 47]

def binary_search(arr, var):
    low = 0
    high = len(arr) - 1
    while low <= high:
        middle = int((low + high)/2)
        if var == arr[middle]:
            return middle
        elif var > arr[middle]:
            low = middle + 1
        elif var < arr[middle]:
            high = middle - 1
        else:
            return "Cant search value"

print(binary_search(li, 22))

- 최적의 시간복잡도 O(1) : 가장 첫번째에 찾고자 하는 데이터가 있는경우

- 최악의 시간복잡도 O(log n) 

이와같이 이진탐색은 매번 배열을 반으로 줄인다. 따라서 시간복잡도가 log n 이 최대이다.