이진 검색

이진 검색

이진 검색은 가장 널리 사용되는 검색 알고리즘이며 효율적이기도 합니다.

세상의 모든 이름이 순서대로 함께 기록되어 있고 특정 이름의 위치를 ​​검색하려는 경우 이진 검색은 최대 35번의 반복으로 이를 수행합니다.

이진 검색은 정렬된 배열에서만 작동합니다. 컬렉션에서 이진 검색을 사용하려면 먼저 컬렉션을 정렬해야 합니다.

이진 검색의 런타임 복잡도는 O(log n)입니다

작동 방식

이진 검색을 시작하기 전에 먼저 범위의 시작과 끝을 찾아야 합니다.

범위의 중간 요소를 비교하여 이진 검색을 시작합니다.

가운데 요소가 대상 요소와 같으면(대상 요소는 범위에서 검색하려는 요소를 의미함) 해당 요소의 인덱스를 반환합니다.

중간 요소가 대상 요소와 일치하지 않으면 범위를 두 부분으로 나눕니다. 전반부는 첫 번째 요소부터 중간 요소까지로 구성되고 후반부는 중간 요소 옆의 요소부터 마지막 ​​요소까지 구성됩니다.

중간 요소가 대상 요소와 일치하지 않으면 중간 요소를 대상 요소와 비교합니다.

대상 요소가 중간 요소보다 크면 시작을 중간+1로 변경하여 후반부에 검색해야 합니다

.

대상 요소가 가운데 요소보다 작으면 끝을 중간-1로 변경하여 전반부에서 검색해야 합니다.

시작 <= 끝이 될 때까지 이 절차를 재귀적으로 반복합니다. 모든 반복에서 대상 요소가 중간 요소와 같으면 중간 요소의 인덱스를 반환합니다. 범위에서 대상 요소를 얻지 못한 경우 -1을 반환합니다.

이진 검색 작동 방식에 대한 간단한 데모



다음은 이진 검색 코드가 어떻게 생겼는지에 대한 샘플입니다.

def BinarySearch(arr, target):
    start = 0       # first element of the range
    end = len(arr) - 1      # last element of the range  
    while start <= end:
        mid = int((start + end) / 2)
        if arr[mid] == target:  # check if target elemtn  is equal to mid if yes … then return mid
            return mid
        if arr[mid] < target:   # if number target element is greater than mid … update start value to mid + 1 and recalculate mid value
            start = mid + 1
        if arr[mid] > target:   # if number target element is less than mid … update end value to mid - 1 and recalculate mid value
            end = mid - 1
    return -1