Python의 이진 검색 설명

이진 검색은 정렬된 배열에서 요소를 검색하는 데 사용되는 검색 알고리즘입니다. 정렬되지 않은 배열에서 검색하는 데 사용할 수 없습니다. 이진 검색은 효율적인 알고리즘이며 시간 복잡성 면에서 선형 검색보다 낫습니다.

선형 탐색의 시간 복잡도는 O(n)입니다. 이진 탐색의 시간 복잡도는 O(log n)입니다. 따라서 이진 검색은 효율적이고 빠른 검색 알고리즘이지만 정렬된 배열에서만 검색할 수 있습니다.

이진 검색은 어떻게 작동합니까?

이진 검색의 기본 개념은 필요한 요소를 배열의 모든 요소와 비교하는 대신 필요한 요소를 배열의 중간 요소와 비교한다는 것입니다. 이것이 우리가 찾고 있는 요소로 판명되면 성공적으로 검색이 완료된 것입니다. 그렇지 않고 찾고 있는 요소가 중간 요소보다 작으면 배열이 정렬되므로 요소가 배열의 첫 번째 또는 왼쪽 절반에 있는 것이 확실합니다. 마찬가지로 찾고 있는 요소가 중간 요소보다 크면 해당 요소가 배열의 후반부에 있는 것이 확실합니다.

따라서 이진 검색은 배열을 계속 절반으로 줄입니다. 위의 과정은 우리가 찾고 있는 요소를 찾을 때까지 배열의 선택된 절반에 재귀적으로 적용됩니다.

배열의 마지막 인덱스와 동일한 왼쪽 인덱스 0과 오른쪽 인덱스로 검색을 시작합니다. 중간 요소 인덱스(mid)는 왼쪽과 오른쪽 인덱스의 합을 2로 나눈 값으로 계산됩니다. 필요한 요소가 중간 요소보다 작으면 오른쪽 인덱스가 mid-1로 변경됩니다. 배열의 전반부만 보고 있습니다. 마찬가지로, 필요한 요소가 중간 요소보다 크면 왼쪽 인덱스가 mid+1로 변경됩니다. 즉, 이제 배열의 두 번째 절반만 볼 수 있습니다. 선택한 어레이 절반에 대해 위의 과정을 반복합니다.

요소가 배열에 없는지 어떻게 알 수 있나요?

요소가 배열에 없음을 나타내는 추가 검색을 중지하려면 몇 가지 조건이 필요합니다. 왼쪽 인덱스가 오른쪽 인덱스보다 작거나 같은 한 배열의 요소를 반복적으로 검색합니다. 이 조건이 거짓으로 바뀌고 아직 요소를 찾지 못하면 배열에 해당 요소가 없다는 의미입니다.

예시

다음 정렬된 배열을 사용하여 요소 6을 검색해야 합니다.

L=0 H=8 중간=4

6<10이므로 전반전을 가져갑니다.

H=중간-1

L=0 H=3 중간=1

6>5, 그러므로 후반부를 선택하십시오.

L=중간+1

L=2 H=3 중간=2

6==6, 발견된 요소

따라서 요소 6은 인덱스 2에 있습니다.

구현

주어진 정렬된 배열에서 필요한 요소를 검색하고 요소가 배열에 있는 경우 해당 인덱스를 인쇄합니다. 요소가 없으면 -1을 인쇄합니다.

바이너리 검색 구현을 위한 코드는 아래와 같습니다.

예시

def binary_search(arr,x):
   l=0
   r=len(arr)-1
   while(l<=r):
      mid=(l+r)//2
      if(arr[mid]==x):
         return mid
      elif(x<arr[mid]):
         r=mid-1
      elif(x>arr[mid]):
         l=mid+1
   return -1
array=[1,2,3,4,5,6,7,8,9,10]
a=7
print(binary_search(array,a))
b=15
print(binary_search(array,b))

출력

6
-1

요소 7은 인덱스 6에 있습니다.

요소 15는 배열에 없으므로 -1이 인쇄됩니다.