[Python] 이분 탐색

[이분탐색 개념]

---

정렬되어 있는 배열에서 데이터를 찾을때, 처음부터 끝까지 데이터를 탐색하는 순차 탐색과는 달리 데이터를 절반으로 줄여가며 탐색하는 알고리즘이다.

 

예를들어, 책에서 127p를 찾을려고 할때 먼저 책의 아무 페이지나 펼친다. 만약 100p를 펼쳤다고 하면 이제 100p 이후에서 원하는 페이지를 찾는다.

 

이렇게 특정 값의 왼쪽과 오른쪽 중에 한 곳을 탐색하는 방법이 이분탐색이다. 보통 특정 값은 배열의 중간에 위치한 값을 사용한다.

 

 

 

[코드]

---

def binary_search(a,x):
    start = 0
    end = len(a) -1

    while start <= end:
        mid = (start + end) // 2
        if a[mid] == x:
            return mid
        elif a[mid] > x :
            end = mid - 1
        else:
            start = mid + 1


d = [1,2,4,6,8,13,35,60]
print(binary_search(d,13))

 

찾고자 하는 값이 a[mid]보다 크면 찾고자하는 값의 범위는 가운데 값보다 뒤에 있으므로 start = mid + 1을 해준다.

찾고자 하는 값이 a[mid]보다 작으면 찾고자하는 값의 범위는 가운데 값보다 앞에 있으므로 end = mid - 1을 해준다.

같으면 값을 return 한다.

 

이때 탐색하는 배열은 정렬되어있어야한다.

 

 

[시간복잡도]

---

이분 탐색의 시간복잡도는 O(logn)으로 순차 탐색의 시간복잡도인 O(n)보다 빠르다.

 

이분탐색을 가능하게 하려면 자료를 미리 정렬해야하는 번거로움이 있지만, 어떤 리스트에서 특정값을 계속 찾아야하는 작업이있다면 효율적인 방법이 될 수 있다.