

Great article, i've found it very usefull, especially problem links at the end (to valladolid, etc.) It should be more of such links. 

What's metabinary search? By searching on Google I just found the expression on another romanian's website :). 

A metabinary search is some kind of binary search where powers of 2 are used. You can look on the source code in the article to figure out. I prefer this version of the binary search because it's easier to code in most of the cases. Yes, romanian folks use to call this kind of search "metabinary search". 

Ah, sounds like a name for radeye's version of binary search, for instance, part of this code. 

Yes, that's the idea. You cand find a shorter implementation in the article. 

That's a terrible name for this idea. There's nothing "meta" about it. 

Mihai Patrascu is the one who used this kind of binary search for the first time (as we know). In the solutions of the problems he proposed for some Romanian olympiads he used to call this kind of search "metabinary search". We just got the name and the idea:) 

>> Mihai Patrascu is the one who used this kind of binary search for the first time
Heh, really? I've been doing it since before he was a gleam in his father's eye. And the idea is obvious enough that I'm sure we can find references back to the 50's and before. 

I think daniel meant that Mihai used it in his code for romanian programming contests and that a lot of romanian high schoolers learned that trick from his code.
Another strange thing is that romanians use the term Lee's algorithm for breadth first search, because of one book published in 95 aimed at programming contests which described bfs as Lee's algorithm. We didn't have CLR back then, it was just published in 2000, and we had poor internet coverage, so that was one of the very few books that dealt with algorithmics.
This is one reason I hate when science is explained in movies, cause it's most of the time very wrong, and a lot of people think it's correct. 

Of course he is not the first using that, the idea is not hard at all. He was just the first who used this idea in Romanian programing contests. Look what Kawigi said: "Ah, sounds like a name for radeye's version of binary search". That's because he first saw this kind of binary search at you. We use to say that this was "Mihai's version of binary search" because we first saw it at him. He gived that name too, and that's why we use it. However, i don't think that we really need to use a special name for this. It's just a binary search after all. 

I also found the article very interesting. I had heard a bit about these two problems but never learned about them in detail before now.
Also, on the binary search topic, it seems that base 3 might be faster than base 2 for doing logarithmicstyle searches. Am I just crazy or do people stick to base 2 because it is easier to code? 

Whether it's easier to code or not, I've thought a bit about problems that require binarysearchlike algorithms, and come to the realization that in order to do an Kary search for the same effect as a binary search, you need to do (K1)*log_{K}N comparisons, and using 2 for K really is optimal when this is the case :) Alternatively, you could have another base X where you do an Xary search among the K choices, but I still think a flat binary search would involve fewer comparisons :) 

Why stop at three? Base N binary search! O(1) running time! 

Well yes but then you have that nasty coefficient of N. 2log3(N) didn't look so bad. Well except I suppose 2log3(N) = 2log2(N)/log2(3), and log2(3) < 2. Darn. I just have this vague memory of a problem where I used something other than a binary search.
Oh actually I guess it was a binary tree type thing or something. But I found the code and the branching factor was set to
int num = (int)(43.66827238/log(lbl));
Which makes me scratch my head a bit and wonder what equation I solved to get that number. 

Thank you for the excellent tutorial . Amazing algorithm :) ! But I got confused at the end of the article, when you wrote: "... From now we will solve the RMQ problem for an array A[0, N  1] where A[i]  A[i + 1] = 1, i = [1, N  1]. We transform A in a binary array with N1 elements, where A[i] = A[i]  A[i + 1]. It's obvious that elements in A can be just +1 or 1. Notice that the old value of A[i] is now the sum of A[1], A[2] .. A[i] plus the old A[0]. However, we won't need the old values from now on.
To solve this restricted version of the problem we need to partition A into blocks of size l = [(log N) / 2]. Let A'[i] be the minimum value for the ith block in A and B[i] be the position of this minimum value in A. Both A and B are N/l long. Now, we preprocess A' using the ST algorithm described in Section. ..."
Then I read the another links in this discussion : http://www.cs.sunysb.edu/~bender/pub/lca.ps First : create A' then, apply ST algorithm for A,A'  and then normalize A  then compute tables for every blocks. ( You normalized the array A at very first of the algorithm  Is that wrong or did I get something wrong ? ) 

You have to normalize the array first, as described in the article. After that, you may use the algorithm described at the end of the article. [LATER EDIT] Note that you don't actually normalize A, this is a forced expresion. You just use LCA queries for computing the RMQ queries on the original vector. For that LCA queries you use RMQ queries on a +1 vector, and that's the vector you process. So, the way that's described in the article, it's necesarry to build the cartesian tree first, and compute the euler tour on it in order to have an <O(n), O(1)> RMQ algorithm. However, don't expect to code this algorithm in a topcoder contest;). It's just too long to code:) 

Yes, It's great. Can you write about suffix tree or suffix array? 

Me and azotlichid have one about suffix arrays in the making, hopefully it will be ready next month. 

Anyone knows what happened to this article? I find the topic very interesting! 
