이진 검색 알고리즘

이진 검색 알고리즘은 원하는 요소 또는 대상 요소에 대해 정렬된 목록을 검색하는 효율적인 알고리즘입니다.

이진 검색은 대상 값을 목록의 중간 요소와 비교하여 작동합니다.
대상 값이 중간 요소보다 크면 목록의 왼쪽 절반이 검색 공간에서 제거되고 오른쪽 절반에서 검색이 계속됩니다.

목표 값이 중간 값보다 작으면 검색 공간에서 오른쪽 절반을 제거하고 왼쪽 절반에서 검색을 계속합니다.

이 프로세스는 중간 요소가 대상 값과 같을 때까지 또는 알고리즘이 요소가 목록에 전혀 없다는 결과를 반환할 때까지 반복됩니다.

The Worst Case Time Complexity is O(log n)

연산:

변수 start는 0으로 설정되고 end는 목록의 길이로 설정됩니다.

변수 start는 검색되는 목록 부분의 첫 번째 요소를 추적하는 반면 end는 검색되는 부분의 끝 다음 요소를 추적합니다.

시작이 끝보다 작은 동안 반복하는 while 루프가 생성됩니다.

mid는 시작과 끝의 평균의 바닥으로 계산됩니다.

인덱스 중간에 있는 요소가 키보다 작으면(즉, 원하는 요소) 시작은 중간 + 1로 설정됩니다.

키보다 크면 끝이 중간으로 설정됩니다.

그렇지 않으면 중간 인덱스에 있는 요소는 찾은 요소의 인덱스로 반환되는 키와 같습니다.

그러한 항목이 없으면 -1이 반환됩니다.

다음 목록이 있다고 가정해 보겠습니다.


목록_항목
21
23
24
35
45
48
56
77
89


색인
0
1
2
삼
4
5
6
7
8


그리고 목록에 24가 있는지 없는지 검색을 원합니다.

알고리즘에 따르면 몇 가지 변수를 설정해야 합니다.
시작 = 0(첫 번째 요소의 인덱스)
end = 8(마지막 요소의 인덱스)
mid = 4 = (0+8)/2 (중간 요소의 인덱스)


목록_항목
21
23
24
35
45
48
56
77
89


색인
0
1
2
삼
4
5
6
7
8

직위
시작

중반

끝


이제 중간 인덱스 즉 48의 현재 값에 따라 변수를 정렬합니다.
인덱스 mid(즉, 48)에 있는 요소가 24보다 작으면 start가 mid + 1로 설정됩니다.
그리고 인덱스 mid(즉, 48)의 요소가 24보다 크면 end는 mid로 설정됩니다.
그렇지 않으면 중간 인덱스에 있는 요소는 발견된 요소의 인덱스로 반환되는 24와 같습니다.

24 < list[mid]임을 분명히 알 수 있으므로 다음과 같이 변경합니다.
시작 = 0 변경 사항 없음
끝 = 4 현재 중간
중간 = 2 = (0+4)/2


목록_항목
21
23
24
35
45
48
56
77
89


색인
0
1
2
삼
4
5
6
7
8

직위
시작

중반

끝




start < end까지 이 과정을 반복합니다. 시작이 끝보다 작으면 해당 평균 요소가 목록에 없습니다.

이제 변수의 현재 위치를 분석하면 24가 중간 지수의 값과 같다는 것을 분명히 알 수 있습니다. 이 인덱스를 반환합니다.

다음은 Python에서 이진 검색 알고리즘을 구현한 것입니다.

def binary_search(mylist, key):
    """Search key in mylist [start... end - 1]."""
    start = 0
    end = len(mylist)
    while start < end:
        mid = (start + end)//2
        if mylist [mid] > key:
            end = mid
        elif mylist [mid] < key:
            start = mid + 1
        else:
            return mid
    return -1


mylist = input[21, 23, 24, 35, 45, 48, 56, 77, 89]
key = 24

index = binary_search(mylist, key)
if index < 0:
    print(key ,' was not found.’)
else:
    print(key , 'was found at index', index)

산출:

24는 인덱스 2에서 발견되었습니다.