Python делит список пополам - PullRequest
Новая
       35

Python делит список пополам

0 голосов
/ 02 ноября 2011

Мне нужно написать функцию, которая берет список и делит его пополам (например, модуль bisect, но я не могу его использовать).Обычно я показываю, что я сделал до сих пор, но я действительно не знаю, как это сделать без модуля, поэтому я надеюсь, что кто-то может мне помочь.Вот точный вопрос, который мне нужно выяснить:

Напишите функцию с именем bisect, которая принимает отсортированный список и целевое значение и возвращает индекс значения в списке, если он есть, или None, если этоне

Ответы [ 2 ]

1 голос
/ 14 января 2012

Я делал домашнее задание из 8-й главы "Think Python", упражнение 8, и я устал от кода выше, написанного Фредом.похоже, есть некоторые ошибки.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)

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

1 голос
/ 02 ноября 2011

Модуль 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)

это в основном выполняет двоичный поиск.Индексы передаются для отслеживания индексов исходного списка при вызовах далее по циклу рекурсии.

...