 Rylai Crestfall -5 years ago 155
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 <= seq:
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? paisanco

You need to change the

& (bitwise "and")

to

and (logical "and")

``````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 <= seq:
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.

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download