二进制搜索圆弧旋转数组

本文介绍了二进制搜索圆弧旋转数组的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

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

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