[자료구조] 이진 탐색 (Binary Search) 파이썬 재귀 반복문

- 이진탐색

 

이진 탐색은 데이터가 정렬되어 있는 배열에서 찾고자 하는 수를 찾아내는 방법이다.

데이터가 정렬되어 있는 배열을 data 라고 정하고

찾고자 하는 수를 target 이라고 하자. 

배열의 중간 인덱스를 mid 로 정한다.

찾고자 하는 수 ( target ) 가 배열의 중간값 ( data[mid] ) 보다 크다면 우측 데이터 대상으로,

찾고자 하는 수 ( target ) 가 배열의 중간값 ( data[mid] ) 보다 작다면 좌측 데이터 대상으로 탐색을 한다.

찾고자 하는 수가 어디에 있냐에 따라 start 와 end의 위치를 변경해준다.

이러한 방법을 반복하여 찾고자 하는 수를 찾을 때까지 반복해 준다.

 

정리하면 이렇게 된다.

▷ target : 찾고자 하는 값

▷ data : 오름차순으로 정렬된 배열(list)

▷ start : data의 처음 값 인덱스

▷ end : data의 마지막 값 인덱스

▷ mid : start, end 의 중간 인덱스

 

---

- 이진 탐색 알고리즘 (반복문 , 재귀)

 

● 반복문 사용

def binary_search(target, data): # 이분탐색
    start = 0
    end = len(data) - 1

    while start <= end:
        mid = (start + end) // 2

        if data[mid] == target:
            return data[mid]
        elif data[mid] < target: # 가운데 기준 오른쪽 구간으로 이동
            start = mid + 1
        else:                    # 가운데 기준 왼쪽 구간으로 이동
            end = mid -1

    return None # 찾는값 없으면 None

 

● 재귀 사용

def binary_search(target, data, start, end):
     if start > end: # 찾는값 없으면 None
        return None
    
     mid = (start + end) // 2
    
     if target == data[mid]:
         return data[mid]
     elif data[mid] < target : # 오른쪽 구간에 대해 재귀 호출
         return binary_search(target, data, mid+1, end)
     else:                     # 왼쪽 구간에 대해 재귀 호출
         return binary_search(target, data, start, mid-1)

 
# print(binary_search(3, [1,2,3,4,5,6,7,8,9,10], 0, 9))

 

 

---

- 이진 탐색 예시

 

반복문을 사용하여 탐색하는 순서를 알아보자.

예를 들어 정렬된 배열 [1,2,3,4,5,6,7,8,9,10] 이 있다 가정한다.

배열의 중간 인덱스(mid)를 찾기 위해 

찾고자하는 배열의 처음 값 인덱스를 start 라고 선언하고, 찾고자하는 배열의 마지막 값 인덱스를 end 라고 선언한다. 

mid 는 배열의 중간이니 (start + end) // 2 이다.

설명은 여기 까지하고 이 배열에서 3 을 찾는 알고리즘을 그림으로 보자.

 

0.   초기 설정은 target = 3 , data = [1,2,3,4,5,6,7,8,9,10]

       start = 0 , end = 9 , mid = 4 로 시작한다.

0단계

1.     target < data[mid] 이니 우리가 찾는 3은 mid의 좌측에 있다는걸 보여준다.

따라서 start = 0,  end = 3, mid = 1 이 된걸 알 수 있다.

1단계

2.    이번엔  target > data[mid] 이니 우리가 찾는 3은 mid 우측에 있다는걸 보여준다.

따라서 start = 2, end = 3, mid = 2 이 된다.

2단계

3. 마지막 while문에서 data[mid] == target 의 결과가 True 이기 때문에

   data[mid] 값을 반환해주면 탐색이 끝이난다.

 

---

- 이진 탐색을 쓰는 이유

 

일반 탐색은 처음부터 탐색하기 때문에 시간복잡도(Time Complexity)가 O(n)이다.

ex ) 배열의 길이가 10000개 라면 worstcase로 O(10000), 즉 10000번의 시간이 걸린다.

 

이진 탐색은 계속 반(N/2) 씩 줄여 나가는 알고리즘이기 때문에 시간 복잡도(Time Complexity)는 O(logN)이다.

ex ) 배열의 길이가 10000개 라면 O(log10000) 이므로 13.xx 번 , 즉 14번 안에는 무조건 찾는다는 알고리즘이다.

 

---

- 쉽게 이해하기

 

[1,2,3,4,5,6,7,8,9,10]  --> 찾고자 하는 값 3

중간 값 = 5   ->   작다   -> [1, 2, 3, 4]

중간 값 = 2   ->   크다   -> [3, 4]

중간 값 = 3   ->   발견   -> [3]