Binary Search 01

Binary Search 이분 검색

이분 검색은 반복적으로 배열을 나누어가며 불필요한 값들을 미리 제거하며 겁색 범위를 좁혀 나가며 원하는 값을 찾아나간다. 이분 검색은 O(log n)의 시간 복잡도를 갖고있다.

Python 예제:

arr = [ 1, 3, 4, 6, 7, 8, 10, 13, 14 ]
x = 4

def binarySearch (arr, l, r, x):
  
    if r >= l: 
    
        mid = l + (r - l) // 2  
        if arr[mid] == x:
            return mid          
        elif arr[mid] > x:
            return binarySearch(arr, l, mid-1, x)  
        else:
            return binarySearch(arr, mid + 1, r, x)
  
    else:
        return -1
        
result = binarySearch(arr, 0, len(arr)-1, x)
  
if result != -1:
    print ("Element is present at index % d" % result)
else:
    print ("Element is not present in array")

찾고자 하는 값을 배열의 중간 값과 비교한다. 만약 배열의 값이 크면 배열의 왼쪽 반과 비교를 계속하고 배열의 값이 작으면 오른쪽 반과 비교를 계속한다. 그리고 값을 찾을때 까지 전 과정을 반복한다.