二分查找循环旋转数组

Question

我正在尝试执行二进制搜索以查找循环排序数组中的元素。我收到一个我似乎不明白的类型错误。任何 suggestions/modifications 将不胜感激。

这是我的代码：

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

除非这是一个学习练习，否则您可能需要改用 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

Answer 2

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

二分查找循环旋转数组

Binary search Circulary rotated array

arrays

rotation

binary-search

circular-list

python-2.7