Syntactic Confectionery Delight PerlMonks

### Re: bit-vector > global minimum

by choroba (Chancellor)
 on Oct 03, 2011 at 16:44 UTC ( #929378=note: print w/ replies, xml ) Need Help??

in reply to bit-vector > global minimum

Just an idea: If a zero follows a 1, it cannot be the minimum. So you can ommit all the zeros preceded by ones (remove them also), recursively. At the end, there are just zeros followed by ones. The last zero is the minimum (or the first 1 if there are no zeros). Does it help?
Update: re-worded (underscored).
Comment on Re: bit-vector > global minimum
Replies are listed 'Best First'.
Re^2: bit-vector > global minimum
by dwm042 (Priest) on Oct 03, 2011 at 17:17 UTC
Choroba,

This algorithm you suggest would fail on a bit vector of 15 1s followed by 5 zeroes.

David.
I updated the algorithm, an important part was missing from the post (silly me). It should work now:
```1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0
1 1 1 1 1 1 1 1 1 1 1 1 1 - - 0 0 0 0
1 1 1 1 1 1 1 1 1 1 1 1 - - - - 0 0 0
1 1 1 1 1 1 1 1 1 1 1 - - - - - - 0 0
1 1 1 1 1 1 1 1 1 1 - - - - - - - - 0
1 1 1 1 1 1 1 1 1 - - - - - - - - - -
^
minimum
Re^2: bit-vector > global minimum
by baxy77bax (Chaplain) on Oct 03, 2011 at 17:20 UTC
but this implies that i would need to do this for every given pair of indexes which would lead to a:

If X = |A[i,j]|, O(X) time algorithm which is higher then my tree solution that runs in O(logX) if i understood you correctly

But never the less, this is a nice trick that didn't cross my mind. Thank you !!!!

Create A New User
Node Status?
node history
Node Type: note [id://929378]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others imbibing at the Monastery: (11)
As of 2016-05-03 15:13 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
What font do you use for programming?

Results (61 votes). Check out past polls.