Python делит список пополам
Мне нужно написать функцию, которая берет список и делит его пополам (например, модуль bisect, но я не могу использовать это). Обычно я показываю, что я сделал до сих пор, но я действительно не знаю, как это сделать без модуля, поэтому я надеюсь, что кто-то может мне помочь. Вот точный вопрос, который мне нужно выяснить:
Напишите функцию с именем bisect, которая принимает отсортированный список и целевое значение и возвращает индекс значения в списке, если он есть, или None, если это не так.
2 ответа
Модуль bisect отслеживает список, сохраняя его отсортированным, без необходимости прибегать каждый раз при вставке элемента. Метод, который вам нужно реализовать, просто нужно искать внутри отсортированного списка.
def bisect(sortedlist,targetvalue,firstindex=0,lastindex=None):
if(len(sortedlist)==0):
return None
if(len(sortedlist)==1):
if(sortedlist[0]==targetvalue):
return firstindex
else:
return None
center = int(round(len(sortedlist)/2))
if(sortedlist[center]==targetvalue):
return firstindex+center
if(targetvalue>sortedlist[center]):
return bisect(sortedlist[center+1:lastindex],targetvalue,center+1,lastindex)
else:
return bisect(sortedlist[0:center],targetvalue,firstindex,center-1)
это в основном делает бинарный поиск. Индексы передаются для отслеживания индексов исходного списка при вызовах далее по циклу рекурсии.
Я делал домашнее задание из упражнения 8 "Think Python", глава 10, и устал от приведенного выше кода, написанного Фредом. кажется, есть некоторые ошибки. 1. счетчик не работает для длинного списка со 100k строк 2. иногда он возвращает None для вещей, которые, я уверен, есть в списке.
так что я немного подправил:
это моя версия:
он работает очень хорошо, он проверил его с помощью списка слов из swampy 2.0 с именем words.txt, который изначально был из коллекции moby: 113809of.fic
надеюсь, это поможет тем из вас, кто борется с программой bisect
def bisects (list,x,counter=0):
if len(list)==0:
return x,'is not in the list'
elif(len(list)==1):
middle = 0
else:
middle = int(len(list)/2)
if x == list[middle]:
return counter, x,'is in the list'
elif x < list[middle]:
counter +=0
return bisects(list[0:middle],x,counter)
elif x > list[middle]:
counter +=middle
return bisects(list[middle+1:],x,counter)
Также будет здорово, если гуру поможет мне исправить этот недостаток, спасибо,