TIL 22. [알고리즘] 이진탐색(Binary Search)

sooo·2020년 10월 25일
0

이진탐색은 오름차순으로 정렬된 데이터의 배열에서 특정한 값을 찾아내는 알고리즘이다. 배열의 가운데 원소부터 시작하여, 찾고자 하는 값과 비교한 후 가운데 원소 값이 찾는 값보다 클 경우 배열의 왼쪽 부분에서 다시 탐색하고, 찾고자 하는 값보다 작을 경우 배열의 오른쪽 부분에서 탐색하는 과정을 반복한다. 원하는 값을 찾거나 더 이상 남은 배열이 없을 경우 탐색을 종료한다.

성능 : O(logN) (한번 반복할 때마다 탐색 범위가 절반씩 줄어듬)

반복문으로 구현(파이썬)

def binary_search(target, data):
    data.sort()
    start = 0
    end = len(data) - 1

    while start <= end:
        mid = (start+end)//2
        
        if data[mid] == target:
            return data[mid]
            break
        elif data[mid] < target:
            start = mid + 1
        else:
            end = mid - 1
            
    return None

0개의 댓글