Re: 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.	[reply]
Re^3: bit-vector > global minimum by choroba (Cardinal) on Oct 03, 2011 at 17:26 UTC
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` [download]	[reply] [d/l]
Re^2: bit-vector > global minimum by baxy77bax (Deacon) 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 !!!!	[reply] [d/l]