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

#python #bisect

#python #разделить пополам

Вопрос:

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

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

1. Это домашнее задание? Я так думаю.

2. Есть ли у вопроса какие-либо ограничения по производительности? Если нет, вы можете просто использовать линейный поиск, если хотите.

3. Я прошу прощения за то, что не понимаю что-то в blender и надеюсь, что смогу встать на правильный путь, и Грег, я не верю, что у него есть ограничения по производительности

4. Мы просто спрашивали, было ли это домашним заданием или нет, потому что довольно редко вас просят повторно реализовать что-то, избегая встроенного модуля, если только это не домашнее задание для проверки понимания.

5. Что вы пробовали? Что произошло, когда вы попробовали это? Вы понимаете, что должен делать модуль bisect? Знаете ли вы, как проверять отдельные элементы списка?

Ответ №1:

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

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

1. Извините, сначала не прочитал комментарии к вопросу. Я немного слишком импульсивен на этом сайте, желая ответить на любой вопрос, не учитывая причину запроса. Давайте просто надеяться, что он научится, посмотрев на мой код, а затем напишет свой собственный.

Ответ №2:

я выполнял домашнее задание из главы 10 «think python», упражнение 8, и мне надоел приведенный выше код, написанный Фредом. похоже, в нем есть некоторые ошибки. 1. счетчик не работает для длинного списка со строками 100 тыс. 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)

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