SORU
17 EKİM 2008, Cuma


İkili arama (ikiye bölme) Python

Bir listede ikili arama yapan bir kütüphane işlevi/bulduysa ve öğenin konumunu demet dönüş yoktur ve 'Yanlış (-1, Hiçbiri, vb.)' değilse?

Fonksiyonları/bisect_left doğru bisect module buldum ama onlar hala öğeyi listede değilse bile bir pozisyon döner. Bu amaçlanan kullanımı için gayet iyi, ama ben sadece bir öğe listesinde olup olmadığını bilmek (bir şey eklemek istemiyorum.

Düşündüm kullanarak bisect_left ve bundan sonra kontrol eğer eşyanın bu pozisyonda eşit ne ben arıyor, ama hantal görünüyor (ve ben de yapayım sınırları ise kontrol numarası olabilir daha büyük daha büyük sayıda listem). Eğer daha iyi bir yöntem varsa bilmek isterim.

EditBu ihtiyacım olan şey açıklamak için bir sözlük bu iş için oldukça uygun olduğunu farkındayım, ama bellek tüketimi mümkün olduğunca düşük tutmaya çalışıyorum. Bu amaçlanan kullanımı çift yönlü-Yukarı Bak tablo bir tür olurdu. Tablodaki değerler listesi var ve değerleri endeksine dayalı erişmek mümkün olmak istiyorum. Ve ayrıca eğer bu değer listesinde ise, belirli bir değer ya da Hiçbiri Endeksi bulmak mümkün olmak istiyorum.

Bunun için bir sözlük kullanarak en hızlı yolu olacaktır, ama (yaklaşık) bellek gereksinimleri çift.

Bu soruyu Python kitaplıkları gözden kaçan bir şey olabileceğini düşünmeye soruyordum. Moe önerdiği gibi kendi kod yazmak zorunda kalacağım gibi görünüyor.

CEVAP
10 ŞUBAT 2010, ÇARŞAMBA


from bisect import bisect_left

def binary_search(a, x, lo=0, hi=None):   # can't use a to specify default for hi
    hi = hi if hi is not None else len(a) # hi defaults to len(a)   
    pos = bisect_left(a,x,lo,hi)          # find insertion position
    return (pos if pos != hi and a[pos] == x else -1) # don't walk off the end

Bunu Paylaş:
  • Google+
  • E-Posta
Etiketler:

YORUMLAR

SPONSOR VİDEO

Rastgele Yazarlar

  • adrianisen

    adrianisen

    25 Kasım 2009
  • Tutorials Junction

    Tutorials Ju

    1 Ocak 2014
  • TWiT Netcast Network

    TWiT Netcast

    27 EKİM 2005