[이진 탐색] 이진 탐색[Binary Search]

정렬된 배열에서 특정 값을 찾아내는 알고리즘이다.

 

 

이진 탐색 설계

 

 

위 설계를 옮긴 코드이다.

 

 

def BSearch(array, check):
    low = 0
    high = len(array) -1

    while(low <= high):
        mid = (low + high) // 2

        if(array[mid] == check):
            return mid

        elif(array[mid] > check):
            high = mid - 1

        else:
            low = mid + 1
    return -1

 

 

시간복잡도는 O(logN)이다.

 

 

 

응용 문제

sojeong-lululala.tistory.com/14

[BOJ] [Python] 13706번 : 제곱근