*The concept described in this article changes a little bit the way we look at the binary search. I have met also a different name of this approach on topcoder pages, where it’s called ***meta-binary search**. The second time I met this algorithm in the **Skiena’s** book **“Algorithms Manual Design”**, where **one-sided binary search** is used to describe it.

Honestly, I prefer the Skiena’s name, as it seems to be more accurate and describe what really happens. The classical binary search algorithm operates on a sub-range of values, like implemented on the related wiki page. As you can see, there is an upper and lower boundary provided, defining the sub-range of the array to be searched. Instead of considering the boundaries and finding the mid point, we can actually consider only the mid point – and this is what the meta binary search does. As an example is better than precept, let’s take a look at some.

Let’s say we have a sorted array and we need to find a given value. Just not to create messy examples, let’s consider the simplest one we can imagine: [1,2,3,4,5,6,7]. If we look for a number six, it will be find at the position 5 (0-indexed array).

In the first step we need to find a value of log N, that will be useful for comparing elements and choosing the proper part of the array to analyse. Of course log is 2-based. We can do it using simple iteration, like this:

int getLogOf(int N)
{
int log2 = 0
while((1 << log2) <= N)log2++;
return --log2;
}

What this value really does, it is explained in the listening below, but in the “human being” words, we may define it as a distance to the next mid element.

Then we can run the search itself, using the following piece of code:

int find(int array[], int N, int K)
{
int log2 = getLogOf(N);
int currentPosition = 0;
while(log2 >= 0)
{
// check if we got a solution
// if yes, the return it
if(array[curPosition] == K)
return curPosition;
// check the next postion
int newPosition = curPosition + (1 << log2);
// if it's smaller or equal then we have to
// update the current position
if(newPosition < N && array[newPosition] <= K)
curPosition = newPosition;
// decrement the skip size
log2--;
}
return -1;
}

So we have an array [1,2,3,4,5,6,7], and we look for 6. Because the size of the array is 7, we know that the log base 2 of 7 is 2 (2^2 = 4, but 2^3 = 8, so we take 2 as the less evil). Let’s see the iterations, the bold element indicates currently considered point:

Iter1: [**1**,2,3,4,5,6,7]

log=2, currentPosition = 0, newPosition = 0 + 2 ^ 2 = 4, array[newPosition] = 5 < 6

currentPosition = newPosition

log--

Iter2: [1,2,3,4,**5**,6,7]

log=1, currentPosition = 4, newPosition = 4 + 2 ^ 1 = 6, array[newPosition] = 7 > 6

log--

Iter2: [1,2,3,4,**5**,6,7]

log=1, currentPosition = 4, newPosition= 4 + 2 ^ 0 = 5, array[newPosition] = 6 == 6

return 5

I hope this article makes you a little bit more familiar with the concept of one sided binary search, that is a very handy tool – **check the top coder lowest common ancestor** article to know why!

Best Regards

Joe Kidd

### Like this:

Like Loading...