Take the 2-minute tour ×

I need to find all the days of the month where a certain activity occurs. The days when the activity occurs will be sequential. The sequence of days can range from one to the entire month, and the sequence will occur exactly one time per month.

To test whether or not the activity occurs on any given day is not an expensive calculation, but I thought I would use this problem learn something new. Which algorithm minimizes the number of days I have to test?

share|improve this question
Here's my idea, prep a binary search tree that divides up the days of the month, eg. 15 as the root node, with 7 and 21 as the nodes under that; etc. Parse the tree until you find a hit, then hop to that element in a list, testing outward from that element. The fewer elements are true, the more efficient this is, though. Any thoughts? –  kreativitea Nov 14 '12 at 18:42
I don't think you're going to do better than @isbadawi mentions, unless you know other information - e.g. are certain days more likely than others, are certain sequence lengths more likely, etc. kreativitea's comment there won't minimize days tested if it's truly random, and would actually add some days to test in that when you find a hit, you need to check both the day before and after, where as a sequential algorithm only requires checking the next date. –  ernie Nov 14 '12 at 18:45
@kreativitea How do you traverse the tree? e.g. you consider node 15 and the test is false. Do you go left or right? –  Ismail Badawi Nov 14 '12 at 18:48
@isbadawi It would be a breadth first search; I guess it's not a binary search tree, it's just a tree. :( –  kreativitea Nov 14 '12 at 18:48
@isbadawi That's true, but the question is "Which algorithm minimizes the number of days I have to test?", not "What is the best way to do this?" The OP seems to understand that any difference in runtime here is academic. He's looking to learn something new. (though itertools and lambda may be new for him, i don't know.) –  kreativitea Nov 14 '12 at 18:54
show 5 more comments

3 Answers

You can't really do much better than iterating through the sequence to find the first match, then iterating until the first non match. You can use itertools to make it nice and readable:

                    itertools.dropwhile(lambda x: not mytest(x), mysequence))
share|improve this answer
@johnthexiii Fixed, thanks –  Ismail Badawi Nov 14 '12 at 18:51
add comment

The best method depends a bit on your input data structure. If your input data structure is a list of booleans for each day of the month then you can use the following code.

start = activity.find(True)
end = activity.rfind(True)
share|improve this answer
add comment

I think the linear probe suggested by @isbadawi is the best way to find the beginning of the subsequence. This is because the subsequence could be very short and could be anywhere within the larger sequence.

However, once the beginning of the subsequence is found, we can use a binary search to find the end of it. That will require fewer tests than doing a second linear probe, so it's a better solution for you.

As others have pointed out, there is not much practical reason for doing this. This is true for two reasons: your large sequence is quite short (only about 31 elements), and you still need to do at least one linear probe anyway, so the big-O runtime will be still be linear in the length of the large sequence, even though we have reduced part of the algorithm from linear to logarithmic.

share|improve this answer
add comment

Your Answer


