알고리즘, 파이썬을 곁들인 (9) - 이분 탐색

이번에는 이분 탐색 알고리즘에 대해 알아보자.

이분 탐색 알고리즘을 작성, 구현해볼 것이다.

---

용어부터 찾아보자.

이분 탐색 알고리즘이란,

이진 검색 알고리즘(binary search algorithm)은 오름차순으로 정렬된 리스트에서 특정한 값의 위치를 찾는 알고리즘이다. 처음 중간의 값을 임의의 값으로 선택하여, 그 값과 찾고자 하는 값의 크고 작음을 비교하는 방식을 채택하고 있다. 처음 선택한 중앙값이 만약 찾는 값보다 크면 그 값은 새로운 최댓값이 되며, 작으면 그 값은 새로운 최솟값이 된다. 검색 원리상 정렬된 리스트에만 사용할 수 있다는 단점이 있지만, 검색이 반복될 때마다 목표값을 찾을 확률은 두 배가 되므로 속도가 빠르다는 장점이 있다.

이라고 한다.

 

정리를 해보자면,

1. 정렬된 리스트에서 특정한 값을 찾는 알고리즘이다.
2. 임의의 중간값을 선택하여, 찾는 값과 크고 작음을 비교한다.
   1. 임의의 중간값이 찾는 값보다 크면, 임의의 중간값을 최대값으로 설정한다.
   2. 임의의 중간값이 찾는 값보다 작으면, 임의의 중간값을 최솟값으로 설정한다.
3. 정렬된 리스트에서만 사용 가능하지만, 굉장히 빠르다.

 

 

 

이게 무슨 말인고 하니.

sorted_nums = [10, 20, 30, 40, 50, 60, 70, 80, 90, 100]

여기 정렬된 sorted_nums List에서 70의 Index 값을 찾아보면서 알아보자.

1. List의 중간에 있는 값을 기준값(여기서는 50)으로 가져온다.
   0(첫 번째 인덱스, 최솟값) + (len(sorted_nums) - 1)(마지막 인덱스, 최댓값) // 2
   
   
2. 50(기준값)과 70(찾는 값)을 비교한다.
3. 50(기준값)보다 70(찾는 값)이 크므로, 50(기준값)을 최솟값으로 다시 지정한다.
   4(50의 인덱스, 최솟값) + (len(sorted_nums) - 1)(마지막 인덱스, 최댓값) // 2
   계산하면 6(값은 70)이 된다.
   
   
4. 70(기준값)과 70(찾는 값)을 비교한다.
5. 기준값과 찾는 값이 같으므로, 인덱스 6을 반환한다.

 

 

 

구현해 보자.

sorted_nums = [10, 20, 30, 40, 50, 60, 70, 80, 90, 100]

# 최소 인덱스, 최대 인덱스를 선언한다.
min_index, max_index = 0, len(sorted_nums) - 1

# 찾으려는 값 70을 선언한다.
find_target = 70

# 찾으려는 값의 인덱스 위치를 -1로 초기화한다.
# 리스트 안에 찾으려는 값이 없으면 -1로 출력된다.
find_index = -1

# 최소 인덱스가 최대 인덱스보다 작거나 같을 때만 반복한다.
while min_index <= max_index:
    
    # 중간 값을 구한다.
    pivot_index = (min_index+max_index) // 2
    
    if find_target == sorted_nums[pivot_index]:
        # 중간 값과 찾는 값이 같으면, index 를 저장하고 반복을 종료한다.
        find_index = pivot_index
        break
        
    elif find_target > sorted_nums[pivot_index]:
        # 중간 값보다 찾는 값이 크면, 중간 인덱스를 최솟값으로 설정한다.
        min_index = pivot_index + 1
        
    else:
        # 중간 값보다 찾는 값이 작으면, 중간 인덱스를 최대값으로 설정한다.
        max_index = pivot_index - 1

print(find_index, sorted_nums[find_index], find_target)

출력 결과 : 

6 70 70

잘 작동하였다.
이진 탐색의 시간 복잡성은 무려 O(log n)이다.

O(log n)은 O(1)의 바로 다음 단계이다. 굉장히 빠른 속도다.

 

 

 

다음 번에 표로 정리해서, 지금까지 알아본 알고리즘들의 시간 복잡성을 비교해보자.

---

출처:

이진 검색 알고리즘 - 위키백과
https://ko.wikipedia.org/wiki/이진_검색_알고리즘

이진 검색 알고리즘 - 위키백과, 우리 모두의 백과사전