L'utilisation d'un dict ne voudrait pas doubler votre utilisation de la mémoire à moins que les objets que vous stockez soient vraiment minuscules, puisque les valeurs ne sont que des pointeurs vers les objets réels:

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

Dans cet exemple, 'foo' n'est stocké qu'une fois. Cela fait-il une différence pour vous? Et de combien d'articles parle-t-on?

ce code fonctionne avec des listes entières de manière récursive. Recherche le scénario le plus simple, qui est: longueur de la liste inférieure à 2. Cela signifie que la réponse est déjà là et qu'un test est effectué pour vérifier la bonne réponse. Si ce n'est pas le cas, une valeur moyenne est définie et testée pour être correcte, si ce n'est pas la section est effectuée en appelant à nouveau la fonction, mais en définissant la valeur moyenne comme la limite supérieure ou inférieure, en la déplaçant vers la gauche ou la droite

def binary_search(intList, intValue, lowValue, highValue):
    if(highValue - lowValue) &lt 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)

consultez les exemples sur Wikipedia 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

'''
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

je suppose que c'est beaucoup mieux et efficace. veuillez me corriger :) . Merci

• s est une liste.
• binary(s, 0, len(s) - 1, find) est l'appel initial.

• la fonction retourne un index de l'article demandé. S'il n'y a pas un tel article, il retourne -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)
  

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

Recherche Binaire:

// 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)

// appel de fonction ci-dessus :

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))

j'avais besoin d'une recherche binaire en python et générique pour les modèles Django. Dans les modèles Django, un modèle peut avoir une clé étrangère à un autre modèle et je voulais effectuer une recherche sur les objets modèles récupérés. J'ai écrit la fonction suivante vous pouvez utiliser cette.

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

beaucoup de bonnes solutions ci-dessus, mais je n'ai pas vu une simple (KISS keep it simple (cause i'm) utilisation stupide du Python construit dans/generic fonction bisect pour faire une recherche binaire. Avec un peu de code autour de la fonction bisect, je pense que j'ai un exemple ci-dessous où j'ai testé tous les cas pour un petit tableau de noms de chaîne. Certaines des solutions ci-dessus font allusion à/disent ceci, mais espérons que le code simple ci-dessous aidera n'importe qui confus comme je l'étais.

Python traversent, est utilisé pour indiquer où insérer une nouvelle valeur/objet de recherche dans une liste triée. Le code ci-dessous qui utilise bisect_left qui retournera l'index du hit si l'élément de recherche dans la liste/tableau est trouvé (note bisect et bisect_right retourneront l'index de l'élément après le hit ou le match comme point d'insertion) si non trouvé, bisect_left retournera un index à l'élément suivant dans la liste triée qui ne sera pas == la valeur de recherche. Le seul autre cas est celui où l'élément de recherche irait fin de la liste où l'index retourné serait au-delà de la fin de la liste/tableau, et qui dans le code au-dessous de la sortie précoce par Python avec des poignées logiques "et". (première condition False Python ne vérifie pas les conditions suivantes)

#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