[자료구조] 이진탐색 (Binary Search)

이진 탐색 = UpDown 게임

 

순차 탐색은 처음부터 끝까지 보면서 탐색하므로 O(N)의 시간이 걸림.

이진 탐색은 배열을 절반으로 계속해서 나누어 mid값이 목표값이 될 때까지 나누게 됨. O(logN)의 시간이 소요됨

 

다만, 이진 탐색은 이미 정렬되어있는 배열에서 탐색해야한다. 그렇지 않으면 정상적으로 동작하지 않음.

 

이진탐색 구현

- python으로 구현하였다.

def BinarySearch (arr,target):
    left = 0
    right = len(arr)-1
    while(True):
        mid = (left+right)//2
        if(arr[mid] == target):
            return mid
        elif(arr[mid] < target):
            left = mid+1
        else:
            right = mid-1
target = 7
arr = [0,1,2,3,4,5,6,7,8,9,10]
result = BinarySearch(arr,target)
print(result)