logo

Python에서 재귀를 사용한 이진 검색

우리는 요소를 발견하는 데 필요한 직접 비교 횟수를 줄이기 위해 이진 검색에서 항목 컬렉션을 두 부분으로 나눕니다. 그러나 한 가지 요구 사항이 있습니다. 배열의 항목을 미리 정렬해야 한다는 것입니다.

이진 검색

그만큼 이진 검색 메소드는 특정 목록 구성원의 색인을 찾습니다. 가장 인기 있고 가장 빠른 알고리즘 중 하나입니다. 이진 검색 절차가 작동하려면 목록의 항목이 정렬되어야 합니다.

단어 빠른 액세스 도구 모음

이진 검색 요소의 인덱스를 찾는 데 있어 보다 효율적인 검색 기술입니다. 선형 검색 모든 목록 색인을 검사할 필요가 없기 때문입니다.

이진 검색 알고리즘의 전체 작업은 다음 단계로 요약될 수 있습니다.

  • 정렬된 배열에서 중간 요소를 찾습니다.
  • 찾을 요소와 중간 요소를 비교합니다.
  • 해당 요소가 주어진 목록의 중간 요소와 같으면 중간 요소의 인덱스가 반환됩니다. 그렇지 않으면 알고리즘은 요소를 중간에 있는 항목과 비교합니다.
  • 이제 찾으려는 요소가 목록의 중간 항목보다 크면 목록의 오른쪽 절반, 즉 중간 인덱스 뒤의 요소와 비교됩니다.
  • 또는 요소가 목록 중간에 있는 요소보다 작으면 목록의 왼쪽 절반, 즉 중간 인덱스 이전의 요소와만 비교됩니다.

재귀 이진 검색

이진 검색은 정렬된 배열의 요소를 찾기 위해 검색 간격을 2개의 동일한 부분으로 지속적으로 나누는 것을 의미하며, 반복 이진 검색은 전체 이진 검색 절차를 더 작은 문제로 나누는 것을 수반합니다. 재귀 이진 검색은 이진 검색에 대한 재귀 답변입니다.

모든 재귀 솔루션이 충족해야 하는 특성은 다음과 같습니다.

  1. 재귀적 접근 방식에는 기본 사례가 필요합니다.
  2. 재귀적 접근 방식에는 재귀적 테스트 케이스가 있어야 합니다.
  3. 재귀적 접근 방식은 기본 사례에 더 가까워져야 합니다.

복잡한 문제의 가장 낮은 세분화는 최종 사례인 기본 사례로 표현됩니다. 따라서 재귀 방법으로 이진 검색을 수행하려면 알고리즘에 기본 사례와 재귀 사례가 포함되어야 하며, 재귀 사례는 기본 사례로 진행됩니다. 그렇지 않으면 프로세스가 완료되지 않고 무한 루프가 발생합니다.

이진 검색 기술은 정렬된 배열 내에서 특정 요소를 찾는 데 걸리는 시간을 줄여줍니다. 이진 검색 방법은 종종 반복적으로 구현되지만 더 작은 조각으로 나누어 재귀적으로 구현할 수도 있습니다.

암호

 #defining a function to execute Binary Search on any given sorted list L. #start is the lowest index of the list being checked at any given time. #end is the highest index of the list being checked at any given time. #item is the item to be searched in the list. def binary_search(L, start, end, item): if end >= start: middle = (start + end) // 2 if L[middle] == item: return middle #middle element is the item to be located #if middle item is greater than the item to be searched, left side of the list will be searched elif L[middle] > item: #starting index will be same but ending index will be the middle of the main list i.e. left half of the list is given in function. return binary_search(L, start, middle - 1, item) else: #if middle item is smaller than the item to be searched, new starting index will be middle of the list i.e. right half of the list. return binary_search(L, middle + 1, end, item) else: #if element is not present in the list return -1 #Drivers code my_list = [ 2, 4, 6, 9, 12, 16, 18, 19, 20, 21, 22 ] element_to_search = 6 print('The given list is') print(my_list) index_of_element = binary_search(my_list, 0, len(my_list)-1, element_to_search) if index_of_element != -1: print('Element searched is found at the index ', str(index_of_element), 'of given list') else: print('Element searched is not found in the given list!') 

산출:

 The given list is [2, 4, 6, 9, 12, 16, 18, 19, 20, 21, 22] Element searched is found at the index 2 of given list 

재귀는 매우 강력한 프로그래밍 및 문제 해결 기술입니다. 간단한 반복 문제부터 복잡한 역추적 문제에 이르기까지 다양한 알고리즘을 평가하고 실행하는 데 이를 사용할 수 있습니다. 이 튜토리얼에서는 Python 언어를 사용하여 재귀 이진 검색 방법을 만드는 방법을 살펴보았습니다.