Binary Searching in 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?

What if the elif statement in your code fails to satisfy the condition? — thefourtheye
– thefourtheye, Commented Mar 16, 2015 at 2:41
At a first glance your & operators should be and operators; you're not doing logical ands, you're doing bitwise ands. — Andrew Magee
– Andrew Magee, Commented Mar 16, 2015 at 2:41
Also it seems binary search won't solve this problem anyway since the input list is not expected to be sorted. — Andrew Magee
– Andrew Magee, Commented Mar 16, 2015 at 2:52
but what does function return on [7, 6, 9, 7, 8]? looks to me like its only returning one element at most, otherwise it would have to append to a result list or it would have to yield, neither of which is being done. — JL Peyret
– JL Peyret, Commented Mar 16, 2015 at 3:02
I think you only need to move around a window of 3 elements through the list and add the index to the result list/iterator if left > current < right — JL Peyret
– JL Peyret, Commented Mar 16, 2015 at 3:04

paisanco · Accepted Answer · 2015-03-16 02:50:04Z

3

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.

answered Mar 16, 2015 at 2:50

paisanco

4,3286 gold badges32 silver badges46 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Blckknght Over a year ago

At first I thought the & would be a harmless error, since True & True is still True. However, the & operator has a higher precedence than comparison operators, so a < b & c < d is interpreted as a < (b & c) < d, causing the problems in the questioner's code.

JL Peyret · Accepted Answer · 2015-03-16 03:23:25Z

seems to work at finding first pit in the given cases. I've tweaked the call to allow multiple functions to be checked.

#.... original find_pit left, but not pasted in
import sys

def find_pit2(seq):

    left = sys.maxint
    maxp = len(seq)

    if maxp == 1 :
        return 0
    else:
        for pos, current in enumerate(seq):
            try:
                right = seq[pos+1]
            except IndexError:
                #rightmost, count as right neighbor as bigger
                right = sys.maxint
            #pit - smaller or equal to neighbours
            if left >= current and current <= right:
                return pos
            left = current


li_f = [find_pit, find_pit2]


for f in li_f:
    print f.__name__

    print("  ",f([0,1]))
    print("  ",f([5, 4, 3, 6, 7]))
    print("  ",f([7, 6, 9, 7, 8]))
    print("  ",f([3, 2, 2, 2, 5, 6, 6, 8]))

giving

find_pit
('  ', 0)
('  ', 2)
('  ', None)
('  ', 3)
find_pit2
('  ', 0)
('  ', 2)
('  ', 1)
('  ', 1)

Collectives™ on Stack Overflow

Binary Searching in Python

2 Answers 2

1 Comment

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Related