Binary Search

Binary Search is a powerful algorithm to search in an ordered collection. It is a divide and conquer algorithm. Its power lies in discarding half of the search space in each iteration, thus, making it logarithmic in running time.

Lets see an example where binary search can be applied.

Finding the leftmost set bit in an integer (32 bit).

Naive approach would be to check each bit from bit position 31 to bit position 0.

int leftmostSetBit(unsigned int x)
{
  unsigned int op = 0x80000000;
  int bitposition = 31;

  while (x & op == 0)
  {
    bitposition--;
    op = op >> 1;
  }

  return bitposition;
}

If the number of bits in an integer is ‘b’ then the naive code has a time complexity of O(b).

We can apply binary search to this problem to find the rightmost set bit in logarithmic time.

Lets see how it works for an 8 bit integer

binsearch

To find the number formed by using an interval of bits we can use a table that will allow for constant time look ups.

A table like this will help.

table

A cell at row i and column j has all the bits set from bit position i to bit position j. We can use this value and use bitwise AND to extract the number between these bit positions.

unsigned int table[32][32];

void populateTable()
{
  unsigned int op;
  int i, j;

  for (i = 0; i < 32; i++)
  {
    op = 1;
    op = op << i;
    for (j = i; j < 32; j++)
    {
      table[i][j] = op;
      op = (op << 1) | op;
    }
  }
}

int leftmostSetBit(unsigned int x)
{
  int low = 0, high = 31;
  int mid;
  unsigned int num;
  unsigned int result;

  while (low < high)
  {
    mid = 1 + (low + high)/2;
    num = table[mid][high];
    result = num & x;

    if (result > 0)
    {
      low = mid;
    }
    else
    {
      high = mid - 1;
    }
  }

  return high;
}

If the number of bits in an integer is ‘b’ then the above code will find the leftmost set bit in O(log b) time complexity.

Binary search is a very powerful algorithm. Most of the common searching problems can be solved by employing it. It just takes a keen eye to figure out how to apply it.

Happy coding.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s