Rylai Crestfall - 10 months ago 66

Python Question

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.

Source (Stackoverflow)