Recherche binaire Réseau à rotation circulaire

Question

J'essaie d'exécuter une recherche binaire pour trouver un élément dans un tableau trié de manière circulaire. Je reçois une erreur de type que je ne semble pas comprendre. Toutes les suggestions/modifications seront appréciées.

voici mon code:

def Binarysearch(a, low, high, x): 
    if low > high: 
     return -1 
    else: 
     mid = (low + high)/2 
     if x == a[mid]: 
      return mid 
     elif a[mid] <= a[high]: 
      if x > a[mid] and x <= a[high]: 
       return Binarysearch(a, mid+1, high, x) 
     elif a[mid] >= a[low]: 
      if x >= a[low] and x < a[mid]: 
       return Binarysearch(a, low, mid-1, x) 

elem_list = [6, 11, 12, 13, 14, 15, 16, 1, 2, 3, 4, 5] 
x = int(raw_input('enter search elemet')) 
lenlist = len(elem_list) 
result = Binarysearch(elem_list, 0, lenlist-1, x) 

if result == -1: 
    print "Not found" 
else: 
    print "Found it", elem_list[result] 

J'obtiens l'erreur:

Line32: TypeError: list indices must be integers, not NoneType 

Answer 1

def rotated_binary_search(A, N, key): 
    L = 0 
    R = N - 1 
    while (L <= R): 
     M = L + ((R - L)/2) 
     if (A[M] == key): return M 
    # the bottom half is sorted 
     if (A[L] <= A[M]): 
      if (A[L] <= key and key < A[M]): 
       R = M - 1 
      else: 
       L = M + 1 
    # the upper half is sorted 
     else: 
      if (A[M] < key and key <= A[R]): 
       L = M + 1 
      else: 
       R = M - 1 
    return -1 

A = [6, 11, 12, 13, 14, 15, 16, 1, 2, 3, 4, 5] 
N = len(A) 
result = rotated_binary_search(A, N, 13) 
print "Original List", A 
if result == -1: 
    print "Not found" 
else: 
    print "Found", A[result], "at position", result`enter code here` 

Résultat:

Original List [6, 11, 12, 13, 14, 15, 16, 1, 2, 3, 4, 5] 
Found 13 at position 3 

Answer 2

moins que ce soit un exercice d'apprentissage, vous pouvez utiliser le module de la place bisect. par exemple.

from bisect import bisect_left 
def search(l, x):         # search x in l 
    if len(l) > 0: 
     p = min((e,i) for i,e in enumerate(l))[1] # min element index 
     p1 = bisect_left(l, x, 0, p)    # search left 
     if p1 < p and l[p1]==x: 
      return p1 
     p2 = bisect_left(l, x, p)     # search right 
     if p2 < len(l) and l[p2]==x: 
      return p2 

démonstration interactive:

>>> elem_list = [6, 11, 12, 13, 14, 15, 16, 1, 2, 3, 4, 5] 
>>> for e in elem_list: 
... assert e == elem_list[search(elem_list, e)] 
... 
>>> for e in [-1, 7, 8, 999]: 
... assert None == search(elem_list, e) 
... 
>>> elem_list.sort() 
>>> elem_list 
[1, 2, 3, 4, 5, 6, 11, 12, 13, 14, 15, 16] 
>>> for e in elem_list: 
... assert e == elem_list[search(elem_list, e)] 
... 
>>> for e in [-1, 7, 8, 999]: 
... assert None == search(elem_list, e) 
... 
>>> assert None == search([], 123) 

Voir aussi

• Binary search (bisection) in Python