[Python] 이진/이분 탐색(Binary Search)

Saemi Min·2023년 2월 25일
0
post-thumbnail

개념

오름차순으로 정렬된 배열에서 찾고자 하는 수(target)를 두 부분으로 나눠서 찾는 알고리즘 기법
순차 탐색(Linear Search)보다 더 빠른 성능을 보인다.

  1. 탐색 리스트가 정렬되어 있지 않으면 정렬
  2. left(리스트 첫번째), right(리스트 마지막), mid(리스트의 중간 값)을 잡는다.
    : 값보단 리스트의 인덱스로 잡는 것이 더 범용적으로 사용할 수 있다.
  3. mid 값과 찾고자 하는 target 값을 비교
  4. mid 값이 더 크면 rigth값을 mid-1로, mid 값이 더 작으면 left 값을 mid+1로 세팅
  5. left > right가 될 때까지 반복

탐색이 계속 1/2씩 줄어들기 때문에 시간 복잡도O(logN)이다.


코드

정방향 구현

def binary_search(arr, value):
    left, right =0, len(arr)

    while left <= right:
        mid = (left+right) //2
        if arr[mid] == value:
            return mid
        if arr[mid] > value:
            right = mid -1
        else:
            left = mid +1
	return None

arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
result_index=binary_search(arr, 3)
print(result_index, arr[result_index])

재귀 함수를 활용한 구현

def binarySearch(array, target, left, right):

	if left > right:
        return None

    mid = (left+right) //2
    
    if target == array[mid]:
        print(mid)
        # return mid
    elif array[mid] > target:
        binarySearch(array, target, left, mid-1)
    else:
        binarySearch(array, target, mid+1, right)

arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
arr.sort()
binarySearch(arr, 3, 0, len(arr))

코드 참고 사이트
개념 참고 사이트

profile
I believe in myself.

0개의 댓글