二进制搜索Circulary旋转阵列

Question

我想执行二进制搜索以查找循环排序数组中的元素。我收到了一个我似乎无法理解的类型错误。任何建议/修改将不胜感激。

这里是我的代码：

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] 

我得到错误：

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` 

结果：

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

Answer 2

除非这是您可能希望使用bisect模块，而不是一个学习锻炼。例如

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 

互动演示：

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

又见

• Binary search (bisection) in Python