이 포스팅에서는 프로그램과 알고리즘을 사용한 Python 이진 검색에 대해 배웁니다.
선형 검색에서는 각 노드/요소를 확인해야 합니다. 이로 인해 시간 복잡도가 증가합니다. 이러한 시간 복잡성을 줄이기 위해 이진 검색을 사용합니다. 이진 검색에서는 단 한 번의 비교 후에 주어진 배열의 절반이 무시됩니다.
주목해야 할 주요 사항은 이진 검색이 정렬된 배열에서만 작동한다는 것입니다.
배열이 오름차순으로 정렬되어 있으면 배열의 중간 인덱스를 찾은 다음 중간 인덱스에 있는 요소와 찾을 요소를 비교하면 됩니다. 주어진 요소가 중간 인덱스의 요소보다 크면 왼쪽 절반 배열을 무시하고 배열은 중간 인덱스의 다음 인덱스에서 시작됩니다.
반면, 주어진 요소가 중간 인덱스에 있는 요소보다 작으면 오른쪽 절반 배열을 무시하고 새 배열은 중간 인덱스의 왼쪽 인덱스로 끝납니다.
주어진 요소가 중간 인덱스에 있는 요소와 동일하면 검색이 완료됩니다.
이 경우 첫 번째 인덱스가 배열의 마지막 인덱스보다 큽니다. 이는 전체 배열을 살펴봤고 주어진 요소가 배열에 표시되지 않음을 의미합니다.
Python 이진 검색
예:
정렬된 배열 [2, 14, 19, 21, 99, 210, 512, 1028, 4443, 5110]이 있고 찾을 요소는 4443입니다.
1 단계:
Python 이진 검색
2 단계:
Python 이진 검색
3단계:
Python 이진 검색
단계:4
Python 이진 검색
연산:
Binary_search [arr, starting index, last index, element]
Step:1- mid = (starting index + last index) / 2
Step:2- If starting index > last index
Then, Print "Element not found"
Exit
Else if element > arr[mid]
Then, starting index = mid + 1
Go to Step:1
Else if element < arr[mid]
Then, last index = mid - 1
Go to Step:2
Else:
{ means element == arr[mid] }
Print "Element Presented at position" + mid
Exit
Python의 이진 검색 프로그램
반복적 접근 방식(루프 사용):
def Binary_search(arr,start_index,last_index,element):
while (start_index<= last_index):
mid =(int)(start_index+last_index)/2
if (element>arr[mid]):
start_index = mid+1
elif (element<arr[mid]):
last_index = mid-1
elif (element == arr[mid]):
return mid
return -1
arr = [2,14,19,21,99,210,512,1028,4443,5110]
element = 4443
start_index = 0
last_index = len(arr)-1
found = Binary_search(arr,start_index,last_index,element)
if (found == -1):
print "element not present in array"
else:
print "element is present at index " + str(found)
산출
요소가 인덱스 8에 존재합니다.
재귀적 접근 방식(재귀 사용):
def Binary_search(arr,start_index,last_index,element):
mid =(int)(start_index+last_index)/2
if(start_index>last_index):
print "Element not found"
elif (element>arr[mid]):
start_index = mid+1
Binary_search(arr,start_index,last_index,element)
elif (element<arr[mid]):
last_index = mid-1
Binary_search(arr,start_index,last_index,element)
else:
print "element is present at index " + str(mid)
arr = [2,14,19,21,99,210,512,1028,4443,5110]
element = 99
start_index = 0
last_index = len(arr)-1
Binary_search(arr,start_index,last_index,element)
산출
요소가 인덱스 4에 존재합니다.
