البحث الثنائي (Bisection) في Python

Question

هل هناك وظيفة مكتبة تؤدي بحثًا ثنائيًا على قائمة/tuple وإرجاع موضع العنصر إذا تم العثور عليه و "false" (-1 ، لا شيء ، إلخ) إذا لم يكن كذلك؟

لقد وجدت وظائف BISECT_LEFT/اليمين في وحدة Bisect, ، لكنهم ما زالوا يعيدون موقفًا حتى لو لم يكن العنصر في القائمة. هذا جيد تمامًا لاستخدامهم المقصود ، لكنني أريد فقط أن أعرف ما إذا كان عنصر ما في القائمة أم لا (لا تريد إدراج أي شيء).

فكرت في استخدام bisect_left ثم التحقق مما إذا كان العنصر الموجود في هذا الموضع مساوياً لما أبحث عنه ، لكن هذا يبدو مرهقًا (وأحتاج أيضًا إلى القيام بالحدود للتحقق مما إذا كان الرقم أكبر من أكبر رقم في قائمتي). إذا كانت هناك طريقة أجمل أود أن أعرفها.

يحرر لتوضيح ما أحتاجه من أجله: أدرك أن القاموس سيكون مناسبًا جدًا لهذا ، لكنني أحاول الحفاظ على استهلاك الذاكرة منخفضًا قدر الإمكان. سيكون استخدامي المقصود نوعًا من طاولة البحث المزدوجة. لدي في الجدول قائمة بالقيم وأحتاج إلى أن أكون قادرًا على الوصول إلى القيم بناءً على فهرسها. وأريد أيضًا أن أكون قادرًا على العثور على فهرس قيمة معينة أو لا شيء إذا لم تكن القيمة في القائمة.

سيكون استخدام قاموس لهذا هو أسرع طريقة ، ولكنه (تقريبًا) يضاعف متطلبات الذاكرة.

كنت أطرح هذا السؤال الذي أفكر في أنني ربما أغفلت شيئًا في مكتبات بيثون. يبدو أنني سأضطر إلى كتابة التعليمات البرمجية الخاصة بي ، كما اقترح Moe.

Answer 1

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

Answer 2

لماذا لا ننظر إلى رمز BISECT_LEFT/يمين وتكييفه ليناسب هدفك.

مثله:

def binary_search(a, x, lo=0, hi=None):
    if hi is None:
        hi = len(a)
    while lo < hi:
        mid = (lo+hi)//2
        midval = a[mid]
        if midval < x:
            lo = mid+1
        elif midval > x: 
            hi = mid
        else:
            return mid
    return -1

Answer 3

هذا أمر خارج عن الموضوع (نظرًا لأن إجابة Moe تبدو كاملة لسؤال البروتوكول الاختياري) ، ولكن قد يكون من المفيد النظر في التعقيد لإجراءك بالكامل من النهاية إلى النهاية. إذا كنت تقوم بتخزين شيء في قوائم مصنفة (وهو المكان الذي سيساعد فيه البحث الثنائي) ، ثم التحقق من وجود الوجود ، فأنت تتكبد (أسوأ حالة ، ما لم يتم تحديد):

قوائم فرز

• o (n log n) لإنشاء القائمة في البداية (إذا كانت بيانات غير مصورة. o (n) ، إذا تم فرزها)
• o (log n) البحث (هذا هو جزء البحث الثنائي)
• o (n) insert / delete (قد يكون O (1) أو o (log n) الحالة المتوسطة ، اعتمادًا على النمط الخاص بك)

بينما مع أ set(), ، أنت تكبد

• س (ن) لإنشاء
• س (1) البحث
• س (1) أدخل / حذف

الشيء الذي تجعلك القائمة المصنفة حقًا "التالي" ، "السابق" ، و "النطاقات" (بما في ذلك إدخال نطاقات أو حذفها) ، والتي هي O (1) أو O (| المدى |) ، مع إعطاء فهرس بدء. إذا كنت لا تستخدم هذه الأنواع من العمليات في كثير من الأحيان ، فإن التخزين كمجموعات ، وقد يكون الفرز للعرض أفضل صفقة بشكل عام. set() يتحمل القليل جدا من النفقات العامة الإضافية في بيثون.

Answer 4

قد تجدر الإشارة إلى أن مستندات Bisect توفر الآن أمثلة البحث:http://docs.python.org/library/bisect.html#searching-sorted-lists

(رفع القيمة بدلاً من العودة -1 أو لا شيء أكثر بيثوني -القائمة.

Answer 5

أبسط هو الاستخدام ينصف وتحقق من موقع واحد مرة أخرى لمعرفة ما إذا كان العنصر موجودًا:

def binary_search(a,x,lo=0,hi=-1):
    i = bisect(a,x,lo,hi)
    if i == 0:
        return -1
    elif a[i-1] == x:
        return i-1
    else:
        return -1

Answer 6

هذا هو الصحيح من الدليل:

http://docs.python.org/2/library/bisect.html

8.5.1. البحث عن قوائم فرز

وظائف Bisect () أعلاه مفيدة لإيجاد نقاط الإدراج ولكن يمكن أن تكون صعبة أو محرجة لاستخدامها في مهام البحث الشائعة. توضح الوظائف الخمس التالية كيفية تحويلها إلى عمليات البحث القياسية للقوائم المرتبة:

def index(a, x):
    'Locate the leftmost value exactly equal to x'
    i = bisect_left(a, x)
    if i != len(a) and a[i] == x:
        return i
    raise ValueError

لذلك مع التعديل الطفيف يجب أن يكون الرمز الخاص بك هو:

def index(a, x):
    'Locate the leftmost value exactly equal to x'
    i = bisect_left(a, x)
    if i != len(a) and a[i] == x:
        return i
    return -1

Answer 7

أوافق على ذلك @إجابة DaveBrahams باستخدام وحدة Bisect هو النهج الصحيح. لم يذكر التفاصيل المهمة في إجابته.

من مستندات bisect.bisect_left(a, x, lo=0, hi=len(a))

لا تتطلب وحدة Bisection أن يتم حساب صفيف البحث مسبقًا في وقت مبكر. يمكنك فقط تقديم نقاط النهاية إلى bisect.bisect_left بدلا من ذلك باستخدام الافتراضيات 0 و len(a).

والأهم من ذلك بالنسبة لاستخدامي ، أبحث عن قيمة x بحيث يتم تقليل الخطأ في وظيفة معينة. للقيام بذلك ، كنت بحاجة إلى وسيلة للحصول على خوارزمية BISECT_LEFT اتصل بحسابي بدلاً من ذلك. هذا بسيط حقا.

مجرد توفير كائن يحدد __getitem__ كما a

على سبيل المثال ، يمكننا استخدام خوارزمية Bisect للعثور على جذر تربيعي بدقة تعسفية!

import bisect

class sqrt_array(object):
    def __init__(self, digits):
        self.precision = float(10**(digits))
    def __getitem__(self, key):
        return (key/self.precision)**2.0

sa = sqrt_array(4)

# "search" in the range of 0 to 10 with a "precision" of 0.0001
index = bisect.bisect_left(sa, 7, 0, 10*10**4)
print 7**0.5
print index/(10**4.0)

Answer 8

إذا كنت تريد فقط معرفة ما إذا كان موجودًا ، فحاول تحويل القائمة إلى قول:

# Generate a list
l = [n*n for n in range(1000)]

# Convert to dict - doesn't matter what you map values to
d = dict((x, 1) for x in l)

count = 0
for n in range(1000000):
    # Compare with "if n in l"
    if n in d:
        count += 1

على جهازي ، "إذا استغرق N في L" 37 ثانية ، في حين أن "إذا استغرق N في D" 0.4 ثانية.

Answer 9

هذا هو واحد:

• غير متكرر (مما يجعله أكثر فعالة الذاكرة من معظم النهج العودية)
• في الحقيقة عمل
• بسرعة منذ ذلك يركض دون أي ضروري إذا والشروط
• بناءً على تأكيد رياضي الذي - التي أرضية (منخفضة + عالية)/2 دائما أصغر من عالي أين قليل هو الحد الأدنى و عالي هو الحد الأعلى.
• تم اختباره: د

---

def binsearch(t, key, low = 0, high = len(t) - 1):
    # bisecting the range
    while low < high:
        mid = (low + high)//2
        if t[mid] < key:
            low = mid + 1
        else:
            high = mid
    # at this point 'low' should point at the place
    # where the value of 'key' is possibly stored.
    return low if t[low] == key else -1

Answer 10

حل ديف أبراهامز جيد. على الرغم من أنني كنت سأفعل ذلك الحد الأدنى:

def binary_search(L, x):
    i = bisect.bisect_left(L, x)
    if i == len(L) or L[i] != x:
        return -1
    return i

Answer 11

على الرغم من عدم وجود خوارزمية بحث ثنائية صريحة في بيثون ، إلا أن هناك وحدة نمطية - bisect - مصممة للعثور على نقطة الإدراج لعنصر في قائمة مصنفة باستخدام بحث ثنائي. يمكن أن يكون "خداع" في إجراء بحث ثنائي. أكبر ميزة في ذلك هي نفس الميزة التي تتمتع بها معظم رمز المكتبة-إنها عالية الأداء ، ويتم اختبارها بشكل جيد وعمل فقط (يمكن أن تكون عمليات البحث الثنائية على وجه الخصوص من الصعب للغاية تنفيذها بنجاح - خاصة إذا لم يتم النظر في حالات الحافة بعناية).

أنواع أساسية

بالنسبة للأنواع الأساسية مثل الأوتار أو INTS ، فمن السهل جدًا - كل ما تحتاجه هو bisect الوحدة النمطية وقائمة مصنفة:

>>> import bisect
>>> names = ['bender', 'fry', 'leela', 'nibbler', 'zoidberg']
>>> bisect.bisect_left(names, 'fry')
1
>>> keyword = 'fry'
>>> x = bisect.bisect_left(names, keyword)
>>> names[x] == keyword
True
>>> keyword = 'arnie'
>>> x = bisect.bisect_left(names, keyword)
>>> names[x] == keyword
False

يمكنك أيضًا استخدام هذا للعثور على التكرارات:

...
>>> names = ['bender', 'fry', 'fry', 'fry', 'leela', 'nibbler', 'zoidberg']
>>> keyword = 'fry'
>>> leftIndex = bisect.bisect_left(names, keyword)
>>> rightIndex = bisect.bisect_right(names, keyword)
>>> names[leftIndex:rightIndex]
['fry', 'fry', 'fry']

من الواضح أنه يمكنك فقط إرجاع الفهرس بدلاً من القيمة في هذا الفهرس إذا رغبت في ذلك.

أشياء

بالنسبة للأنواع أو الكائنات المخصصة ، تكون الأمور أكثر صعوبة قليلاً: يجب عليك التأكد من تنفيذ طرق المقارنة الغنية للحصول على Bisect للمقارنة بشكل صحيح.

>>> import bisect
>>> class Tag(object):  # a simple wrapper around strings
...     def __init__(self, tag):
...         self.tag = tag
...     def __lt__(self, other):
...         return self.tag < other.tag
...     def __gt__(self, other):
...         return self.tag > other.tag
...
>>> tags = [Tag('bender'), Tag('fry'), Tag('leela'), Tag('nibbler'), Tag('zoidbe
rg')]
>>> key = Tag('fry')
>>> leftIndex = bisect.bisect_left(tags, key)
>>> rightIndex = bisect.bisect_right(tags, key)
>>> print([tag.tag for tag in tags[leftIndex:rightIndex]])
['fry']

يجب أن يعمل هذا في Python 2.7 -> 3.3 على الأقل

Answer 12

لا يحب استخدام DICT ضعف استخدام الذاكرة الخاص بك ما لم تكن الكائنات التي تخزنها صغيرة جدًا ، لأن القيم ليست سوى مؤشرات للكائنات الفعلية:

>>> a = 'foo'
>>> b = [a]
>>> c = [a]
>>> b[0] is c[0]
True

في هذا المثال ، يتم تخزين "فو" مرة واحدة فقط. هل هذا يحدث فرقا بالنسبة لك؟ وعدد العناصر التي نتحدث عنها على أي حال؟

Answer 13

يعمل هذا الرمز مع قوائم عدد صحيح بطريقة عودية. تبحث عن أبسط سيناريو للحالة ، وهو: طول القائمة أقل من 2. يعني أن الإجابة موجودة بالفعل ويتم إجراء اختبار للتحقق من الإجابة الصحيحة. إذا لم يكن الأمر كذلك ، يتم تعيين القيمة المتوسطة واختبارها لتكون صحيحة ، إذا لم يتم تنفيذ التشريح عن طريق الاتصال بالوظيفة مرة أخرى ، ولكن ضبط القيمة المتوسطة كحدود علوية أو أقل ، عن طريق تحويلها إلى اليسار أو اليمين

def binary_search(intList, intValue, lowValue, highValue):
    if(highValue - lowValue) < 2:
        return intList[lowValue] == intValue or intList[highValue] == intValue
    middleValue = lowValue + ((highValue - lowValue)/2)
    if intList[middleValue] == intValue:
        return True
    if intList[middleValue] > intValue:
        return binary_search(intList, intValue, lowValue, middleValue - 1)
   return binary_search(intList, intValue, middleValue + 1, highValue)

Answer 14

تحقق من الأمثلة على ويكيبيديا http://en.wikipedia.org/wiki/binary_search_algorithm

def binary_search(a, key, imin=0, imax=None):
    if imax is None:
        # if max amount not set, get the total
        imax = len(a) - 1

    while imin <= imax:
        # calculate the midpoint
        mid = (imin + imax)//2
        midval = a[mid]

        # determine which subarray to search
        if midval < key:
            # change min index to search upper subarray
            imin = mid + 1
        elif midval > key:
            # change max index to search lower subarray
            imax = mid - 1
        else:
            # return index number 
            return mid
    raise ValueError

Answer 15

'''
Only used if set your position as global
'''
position #set global 

def bst(array,taget): # just pass the array and target
        global position
        low = 0
        high = len(array)
    while low <= high:
        mid = (lo+hi)//2
        if a[mid] == target:
            position = mid
            return -1
        elif a[mid] < target: 
            high = mid+1
        else:
            low = mid-1
    return -1

أعتقد أن هذا أفضل بكثير وفعال. رجاء صحح لي :) . شكرًا لك

Answer 16

• s هي قائمة.
• binary(s, 0, len(s) - 1, find) هي المكالمة الأولية.

• تُرجع الدالة فهرس العنصر المستكشف. إذا لم يكن هناك عنصر من هذا القبيل ، فإنه يعود -1.

  def binary(s,p,q,find):
      if find==s[(p+q)/2]:
          return (p+q)/2
      elif p==q-1 or p==q:
          if find==s[q]:
              return q
          else:
              return -1
      elif find < s[(p+q)/2]:
          return binary(s,p,(p+q)/2,find)
      elif find > s[(p+q)/2]:
          return binary(s,(p+q)/2+1,q,find)
  

Answer 17

def binary_search_length_of_a_list(single_method_list):
    index = 0
    first = 0
    last = 1

    while True:
        mid = ((first + last) // 2)
        if not single_method_list.get(index):
            break
        index = mid + 1
        first = index
        last = index + 1
    return mid

Answer 18

بحث ثنائي :

// List - values inside list
// searchItem - Item to search
// size - Size of list
// upperBound - higher index of list
// lowerBound - lower index of list
def binarySearch(list, searchItem, size, upperBound, lowerBound):
        print(list)
        print(upperBound)
        print(lowerBound)
        mid = ((upperBound + lowerBound)) // 2
        print(mid)
        if int(list[int(mid)]) == value:
               return "value exist"
        elif int(list[int(mid)]) < value:
             return searchItem(list, value, size, upperBound, mid + 1)
        elif int(list[int(mid)]) > value:
               return searchItem(list, value, size, mid - 1, lowerBound)

// لاستدعاء الوظيفة أعلاه استخدام:

list = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
searchItem = 1        
print(searchItem(list[0], item, len(list[0]) -1, len(list[0]) - 1, 0))

Answer 19

كنت بحاجة إلى البحث الثنائي في بيثون وعامة لنماذج Django. في نماذج Django ، يمكن أن يكون لدى نموذج واحد مفتاح خارجي لنموذج آخر وأردت إجراء بعض البحث على كائنات النماذج التي تم استردادها. لقد كتبت الوظيفة التالية يمكنك استخدام هذا.

def binary_search(values, key, lo=0, hi=None, length=None, cmp=None):
    """
    This is a binary search function which search for given key in values.
    This is very generic since values and key can be of different type.
    If they are of different type then caller must specify `cmp` function to
    perform a comparison between key and values' item.
    :param values:  List of items in which key has to be search
    :param key: search key
    :param lo: start index to begin search
    :param hi: end index where search will be performed
    :param length: length of values
    :param cmp: a comparator function which can be used to compare key and values
    :return: -1 if key is not found else index
    """
    assert type(values[0]) == type(key) or cmp, "can't be compared"
    assert not (hi and length), "`hi`, `length` both can't be specified at the same time"

    lo = lo
    if not lo:
        lo = 0
    if hi:
        hi = hi
    elif length:
        hi = length - 1
    else:
        hi = len(values) - 1

    while lo <= hi:
        mid = lo + (hi - lo) // 2
        if not cmp:
            if values[mid] == key:
                return mid
            if values[mid] < key:
                lo = mid + 1
            else:
                hi = mid - 1
        else:
            val = cmp(values[mid], key)
            # 0 -> a == b
            # > 0 -> a > b
            # < 0 -> a < b
            if val == 0:
                return mid
            if val < 0:
                lo = mid + 1
            else:
                hi = mid - 1
    return -1

Answer 20

العديد من الحلول الجيدة أعلاه ، لكنني لم أر (قبلة تبقيها بسيطة (لأنني) استخدام غبي لوظيفة الثعبان المدمجة/العامة للقيام بالبحث الثنائي. مع القليل من التعليمات البرمجية حول وظيفة Bisect ، أعتقد أن لدي مثالًا أدناه حيث اختبرت جميع الحالات لمجموعة سلسلة صغيرة من الأسماء. بعض الحلول المذكورة أعلاه تلمح/قول هذا ، ولكن نأمل أن يساعد الكود البسيط أدناه أي شخص في الخلط كما كنت.

يتم استخدام Python Bisect للإشارة إلى مكان إدراج عنصر قيمة/بحث جديد في قائمة مصنفة. الرمز أدناه الذي يستخدم BISECT_LEFT الذي سيعود فهرس الضربة إذا تم العثور على عنصر البحث في القائمة/الصفيف (لاحظ BISECT و BISECT_RIGH ، سيقوم BISECT_LEFT بإرجاع فهرس إلى العنصر التالي في القائمة المرتبة التي لن == قيمة البحث. الحالة الأخرى الوحيدة هي المكان الذي سيذهب فيه عنصر البحث في نهاية القائمة التي يتم فيها إرجاع الفهرس إلى ما بعد نهاية القائمة/الصفيف ، والتي في الكود أدناه المخرج المبكر بواسطة Python مع "و" المقابض المنطقية ". (الشرط الأول Python الخاطئ لا يتحقق من الشروط اللاحقة)

#Code
from bisect import bisect_left
names=["Adam","Donny","Jalan","Zach","Zayed"]
search=""
lenNames = len(names)
while search !="none":
    search =input("Enter name to search for or 'none' to terminate program:")
    if search == "none":
        break
    i = bisect_left(names,search)
    print(i) # show index returned by Python bisect_left
    if i < (lenNames) and names[i] == search:
        print(names[i],"found") #return True - if function
    else:
        print(search,"not found") #return False – if function
##Exhaustive test cases:
##Enter name to search for or 'none' to terminate program:Zayed
##4
##Zayed found
##Enter name to search for or 'none' to terminate program:Zach
##3
##Zach found
##Enter name to search for or 'none' to terminate program:Jalan
##2
##Jalan found
##Enter name to search for or 'none' to terminate program:Donny
##1
##Donny found
##Enter name to search for or 'none' to terminate program:Adam
##0
##Adam found
##Enter name to search for or 'none' to terminate program:Abie
##0
##Abie not found
##Enter name to search for or 'none' to terminate program:Carla
##1
##Carla not found
##Enter name to search for or 'none' to terminate program:Ed
##2
##Ed not found
##Enter name to search for or 'none' to terminate program:Roger
##3
##Roger not found
##Enter name to search for or 'none' to terminate program:Zap
##4
##Zap not found
##Enter name to search for or 'none' to terminate program:Zyss
##5
##Zyss not found