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) 

Также будет здорово, если гуру поможет мне исправить этот недостаток, спасибо,

Другие вопросы по тегам