요소가 SORTED 목록에 있는지 확인하는 재귀 함수

Question

나는 실제로 재귀 함수에 관심이 없으며 재귀 및 더 최적의 기능으로 내 기능을 변경하도록 요청하고 있습니다. 이 작업에서이 목록이 정렬되어 있다는 사실을 활용해야한다는 것을 알고 있습니다. 그러나 방법을 모르겠습니다. 아마도 거품 정렬일까요? 이것은 매우 간단하지만 재귀 적이 지 않은 내 코드이며 목록이 정렬되었는지 여부를 고려하지 않습니다.

list1 = [1, 2, 3, 4, 5, 6]


def is_in_List(x):
    if x in list1:
        return True
    else:
        return False


x = 3

if is_in_List(x):
    print(f"{x} is in list")
else:
    print(f"{x} is not in list")

Answer 1

당신이 할 수있는 것은 devide와 conquer를 사용하는 것입니다.

알고리즘은 다음과 같습니다.

총 n 개의 요소가 정렬 된 목록이 있습니다. n / 2의 요소가 찾고있는 요소인지 확인 배열 그렇지 않은 경우 정렬 된 목록 인 경우 n / 2-> n의 모든 요소가 더 크고 0의 모든 요소가 더 크다는 것을 알고 있습니다. -> n / 2가 더 작습니다. n / 2의 숫자가 검색하려는 숫자보다 적거나 많은지 확인하십시오. 더 적 으면 같은 함수를 다시 실행하지만 이제 목록의 하위 집합 만 제공합니다. 즉, 더 작 으면 0-> n / 2를 제공하고 더 크면 n / 2-> n을 제공합니다. . 물론 당신은 몇 가지 중지 조건이 필요하지만 헤이, 이것이 알고리즘입니다.

그것이 이론입니다. 여기에 코드가 있습니다.

내 마음의 꼭대기에서 최고의 구현이 아닙니다.

my_list = [1,2,3,4,5,6,7,8,9];


def binary_search(a_list, search_term):

    #get the middle position of the array and convert it to int    
    middle_pos = int((len(a_list)-1)/2)
    
    #check if the array has only one element, and if so it it is not equal to what we're searching for, than nothing is in the aray
    
    if len(a_list) == 1 and search_term != a_list[middle_pos] :
        #means there are no more elements to search through
        return False
    
    #get the middle term of the list
    middle_term = a_list[middle_pos]
    
    #check if they are equal, if so, the number is in the array
    if search_term == middle_term:
        return True
    
    #if the middle is less than search, it means we need to search in the list from middle to top
    if middle_term < search_term : 
        #run the same algo, but now on a subset of the given list
        return binary_search(a_list[middle_pos:len(a_list)], search_term)
        
    else : 
        #on else, it means its less, we need to search from 0 to middle
        #run the same algo, but now on a subset of the given list
        return binary_search(a_list[0:middle_pos], search_term)
        
print(binary_search(my_list, 1)