이진탐색(Binary Search)

이진 탐색이란 정렬된 리스트에서 검색 값을 찾아내는 알고리즘이다. 배열의 중간에 있는 임의의 값을 선택하여 찾고자 하는 값 X와 비교한다. X가 중간 값보다 작으면 중간 값을 기준으로 좌측의 데이터들을 대상으로, X가 중간값보다 크면 배열의 우측을 대상으로 다시 탐색한다. 동일한 방법으로 다시 중간의 값을 임의로 선택하고 비교한다. 해당 값을 찾을 때까지 이 과정을 반복한다.

과정

1. 배열의 중간 값을 가져온다.
2. 중간 값과 찾을 값을 비교한다
   2-1. 중간 값이 검색 값과 같으면 종료
   2-2. 중간 값보다 검색 값이 크면 중간 값 기준으로 배열의 오른쪽 구간을 탐색
   2-3. 중간 값보다 검색 값이 작다면 중간 값 기준 배열의 왼쪽 구간을 탐색
3. 값을 찾거나 더 이상 배열이 남지 않을때까지 반복한다.

❌종료 조건❌

• 검색을 성공한 경우 : 리스트에서 검색할 값을 찾았을 때 종료된다
• 검색을 실패한 경우 : 더 이상 검색할 범위가 없을 경우 종료된다

예시

오름차순으로 정렬된 배열 {16, 20, 33, 46, 57, 66, 78, 87, 96}에서 이진 탐색을 이용해 33을 찾는다고 한다.
1. 중간값인 57을 기준으로 33과 비교한다. 33이 더 작으므로 중간값기준으로 왼쪽 부분을 탐색한다.
2. {16, 20, 33, 46}에서 중간값 20을 기준으로 33과 비교한다. 33이 더 크므로 중간값 기준으로 오른쪽 부분을 탐색한다.
3. {33, 46}에서 중간값 33을 기준으로 보면 찾을 값과 동일하므로 종료된다.

시간 복잡도

n개의 값이 있다고 하면 n, n/2, n/4, ..., 2, 1번 비교하기 때문에 최선의 경우는 O(1), 최악의 경우는 O(log n)이다.

장/단점

• 장점
  검색이 반복될 때마다 검색 범위가 절반으로 줄어들기 때문에 속도가 빠르다
• 단점
  정렬된 리스트에만 사용할 수 있다

구현

• 재귀 함수

def binary_search(target, start, end, data) :
    if start>end :
        return -1

    mid=(start+end)//2

    if data[mid] == target :
        return mid
    elif data[mid] > target:
        end=mid-1
    elif data[mid] < target:
        start=mid+1

    return binary_search(target, start, end, data)

data=[16, 20, 33, 46, 57, 66, 78, 87, 96]
target=33
index=binary_search(target, 0, len(data)-1, data)
print(index)

• 반복문

data=[16, 20, 33, 46, 57, 66, 78, 87, 96]
target=33
start=0
end=len(data)-1
index=-1
while start<end :
    mid=(start+end)//2

    if data[mid]==target:
        index=mid
        break
    elif data[mid]<target :
        start=mid+1
    else:
        end=mid-1

print(index)