Fungsi rekursif untuk memeriksa apakah elemen dalam daftar SORTED
Saya tidak benar-benar menjadi fungsi rekursif dan saya meminta untuk mengubah fungsi saya menjadi fungsi rekursif dan lebih optimal. Saya tahu bahwa dalam tugas ini saya harus memanfaatkan fakta bahwa daftar ini diurutkan, tetapi saya tidak tahu caranya, mungkin semacam gelembung? Ini adalah kode saya, cukup sederhana tetapi bahkan tidak rekursif dan tidak memperhitungkan apakah daftar diurutkan atau tidak.
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")
Jawaban
yang bisa Anda lakukan adalah menggunakan devide and conquer, yang artinya:
Algo berjalan seperti ini:
Anda memiliki daftar yang diurutkan dari n total elemen. Checkin array jika elemen pada n / 2 adalah yang Anda cari Jika tidak, menjadi daftar yang diurutkan, Anda tahu bahwa semua elemen dari n / 2 -> n lebih besar, dan semua elemen dari 0 -> n / 2 lebih kecil. Periksa apakah angka di n / 2 kurang atau lebih dari yang Anda cari. Jika kurang, Anda menjalankan fungsi yang sama lagi, tetapi sekarang Anda hanya memberikan subset dari list, artinya jika lebih kecil Anda memberi 0 -> n / 2, jika lebih besar Anda memberi n / 2 -> n . Tentu saja Anda memerlukan beberapa kondisi yang menghentikan tapi hei, ini algo.
Itu teorinya, ini kodenya.
Bukan implementasi terbaiknya, hanya dari atas pikiran saya.
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)