Binary search Circulary rotated array

Question

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.

here is my code:

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]

I get error:

Line32: TypeError: list indices must be integers, not NoneType

not a complete answer, but try changing `and` to `or` in the `if` checks — chickity china chinese chicken, Sep 16 '17 at 21:28
tried that. did get rid of the error, but it still can't find the element — suyash gautam, Sep 18 '17 at 04:19
Also, try change `def Binarysearch(a, low, high, x): if low > high: return low` — chickity china chinese chicken, Sep 18 '17 at 05:28

score 1 · Answer 1 · answered Sep 16 '17 at 22:20

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

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

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]:
...    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)

See also

Binary search (bisection) in Python

thanks for the feedback. Really appreciate that. i will try that. Although, I would be really happy if I could apply a solution that is more general and can be used in any language as well as python. — suyash gautam, Sep 18 '17 at 04:22
The min operation runs in $O(N)$ so this is not as optimal as the solution @suyashgautam posted which runs in $O(\log (N))$ — Adithya, Aug 07 '22 at 18:53

score 0 · Accepted Answer · answered Sep 19 '17 at 02:23

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`

Result:

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

Binary search Circulary rotated array

2 Answers2