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 ap

Solution 1:

Unless this is a learning exercise you may want to use the bisect module instead. e.g.

from bisect import bisect_left
defsearch(l, x):                                 # search x in liflen(l) > 0:
        p = min((e,i) for i,e inenumerate(l))[1] # min element index
        p1 = bisect_left(l, x, 0, p)              # search leftif p1 < p and l[p1]==x:
            return p1
        p2 = bisect_left(l, x, p)                 # search rightif p2 < len(l) and l[p2]==x:
            return p2

interactive demonstration:

>>>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]:...assertNone == 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]:...assertNone == search(elem_list, e)...>>>assertNone == search([], 123)

See also

• Binary search (bisection) in Python

Solution 2:

defrotated_binary_search(A, N, key): 
    L = 0
    R = N - 1while (L <= R): 
        M = L + ((R - L) / 2)
        if (A[M] == key): return M
    # the bottom half is sortedif (A[L] <= A[M]):
            if (A[L] <= key and key < A[M]):
                R = M - 1else:
                L = M + 1# the upper half is sortedelse: 
            if (A[M] < key and key <= A[R]):
                L = M + 1else:
                R = M - 1return -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`

Result:

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