Binary Search (python)

Binary Search

• 중앙값을 사용해 검색 범위를 반으로 줄여가면서 빠르게 검색을 수행함.
• 시간복잡도: O(log n)
• 이진 검색을 하기 위해서는 자료가 정렬, 오름차순 상태여야 한다.

검색과정

1. 자료의 중앙에 있는 원소를 고른다
2. 중앙의 원소의 값과 찾고자 하는 목표 값을 비교한다
3. 목표 값이 중아에 원소 값보다 작다면 자료의 왼쪽을, 크다면 자료의 오른쪽에 대해서 새로 검색을 수행한다

Code

arr = [2, 4, 7, 9, 11, 19, 13]
# 정렬을 무조건 해야함
arr.sort()

def binarySearch(target):
    low =0
    high= len(arr) -1

    # low > high라면 데이터를 못찾은 경우
    while low <= high:
        mid = (low + high) //2

        # 가운데 값이 정답인 경우
        if arr[mid]==target:
            return mid
        # 가운데 값이 정답보다 작은경우
        elif arr[mid] < target:
            low = mid+1
        # 가운데 값이정답보다 큰 경우
        else:
            high= mid -1

    # 해당데이터를 찾지 못한 경우
    return -1

Code(recursion)

# 이진검색 - 재귀호출
arr = [2, 4, 7, 9, 11, 19, 13]
# 정렬을 무조건 해야함
arr.sort()

# 함수 한 번 호출 때 마다 low, high 변수가 바뀌어서 사용됨
def binarySearch(low, high, target):

    # 데이터를 못 찾을때
    if low > high:
        return -1

    mid = (low+high) //2
    #1. 가운데 값이 정답인 경우
    if target== arr[mid]:
        return mid

    #2. 가운데 값이 정답보다 작은 경우
    elif arr[mid] < target:
        return binarySearch(mid+1, high, target)
    
    #3. 가운데 값이 정답보다 큰 경우
    else:
        return binarySearch(low, mid-1, target)