二进制搜索圆弧旋转数组 [英] Binary search Circulary rotated array

问题描述

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

I am trying to execute a Binary search to find an element in a circularly sorted array. I get a type error that I don't seem to understand. Any suggestions/modifications will be appreciated.

这是我的代码:

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

推荐答案

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

这篇关于二进制搜索圆弧旋转数组的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！