이진 탐색 (이분 탐색) (Binary Search)

이진탐색은 반드시 정렬된 배열에서만 사용 가능한 점에 주의하자.

이진탐색은 순차 검색이며 시간복잡도는 O(log N)이다.

 

다음은 파이썬으로 구현한 코드이다.

# arr   : 정렬된 리스트
# target: 찾고자 하는 값
# start : 배열의 처음
# end   : 배열의 마지막
# binary_serach 함수의 반환값 : target의 인덱스

def binary_search(arr, target, start, end):
    if start > end:
       return None
    
    mid = (start + end ) // 2
    
    if arr[mid] == target:
        return mid
    elif arr[mid] > target:
        end = mid - 1
    else:
        start = mid + 1

    return binary_search(arr, target, start, end)

arr.sort()  # 리스트가 정렬되지 않았을 경우
binary_search(arr, target, 0, len(arr))