Rylai Crestfall Rylai Crestfall - 4 months ago 21
Python Question

Binary Searching in Python

So I have this problem.


You are given a landscape in the form of a non-empty one-dimensional
array seq. The goal is to find an index i of a cell that is a pit. We
say seq[i] is a pit if seq[i] <= seq[i-1] and seq[i] <= seq[i+1]. For
example in the array [7, 6, 9, 7, 8], the indices 1 and 3 are pits.
The first or last elements are considered to be a pit if they are less
than or equal to their only neighbour. For example the last element of
[3, 2, 4, 4, 1] is a pit (and also index 1). Note that the definition
of a pit, also includes equality; for example in [3, 2, 2, 2, 5, 6, 6,
8], the indices 1, 2, 3, and 6 are pits. As a special case, we also
define the only cell of an array of length one to be a pit as well.


I've formulated a solution using a binary search (kind of) to achieve O(logn) as the worst case time. But I've encountered an example which returns nothing or NONE.

def find_pit(seq):
first = 0
last = len(seq) - 1
origlast = last
mid = 0
if len(seq) == 1 :
return 0
else:
while first <= last & mid < last :
mid = (first + last) // 2
if seq[mid] <= seq[mid - 1] & seq[mid] <= seq[mid + 1]:
return mid
else:
if seq[mid] > seq[mid - 1]:
last = mid
else:
first = mid
if seq[0] <= seq[1]:
return 0
elif seq[origlast] <= seq[origlast-1]:
return (len(seq) - 1)

print(find_pit([0,1]))
print(find_pit([5, 4, 3, 6, 7]))


How do I fix this?

Answer

You need to change the

& (bitwise "and")

to

and (logical "and")

in your code:

def find_pit(seq):
    first = 0
    last = len(seq) - 1
    origlast = last
    mid = 0
    if len(seq) == 1 :
        return 0
    else:
        #change next line to use logical and
        while first <= last and mid < last :  
            mid = (first + last) // 2
            #change next line to use logical and
            if seq[mid] <= seq[mid - 1] and seq[mid] <= seq[mid + 1]:
                return mid
            else:
                if seq[mid] > seq[mid - 1]:
                    last = mid
                else:
                    first = mid
    if seq[0] <= seq[1]:
        return 0
    elif seq[origlast] <= seq[origlast-1]:
        return (len(seq) - 1)


print(find_pit([0,1]))
print(find_pit([5, 4, 3, 6, 7]))

Running this with the above test cases will now give the result: 0 for the first list and 2 for the second.

Comments