Ronzii's Blog

Just your average geek's blog

Binary Search in a Matrix

This algorithm uses divide and conquer to divide the matrix into two parts. This algorithm has an average complexity of o((logn)^2). Therefore, it performs better than step wise search from a corner(O(m+n)).

  1. Let us assume we are searching for target. 
  2. Find i,j along the middle column(j) such that a[i][j]<target<a[i+1][j] using binary search.
  3. Divide into 2 parts along this co-ordinate
#include <iostream>
#define MAX 5
using namespace std;
//  T(n) = 2T(n/2) + c lg n
// Column Partition
bool binaryPartition(int a[][MAX],int r, int c, int R, int C, int target)
{
    if(c>C || r>R) return false;
    if(target<a[r][c] || target>a[R][C]) return false;
    int mid = c + (C-c)/2;
    int row = r;
    // Binary search position where a[i] < target < a[i+1]
    while(row<=R && a[row][mid]<=target)
    {
        if(a[row][mid]==target) return true;
        row++;
    }
    // Divide into 2 parts
    return binaryPartition(a,row,c,R,mid-1,target) || binaryPartition(a,r,mid+1,row-1,C,target);
}
bool binaryPartition(int a[][MAX], int M, int N, int target)
{
    return binaryPartition(a,0,0,M-1,N-1,target);
}
int main()
{
    int a[MAX][MAX] = {{1,4,7,11,15},{2,5,8,12,19},{3,6,9,16,22},{10,13,14,17,24},{18,21,23,26,30}};
    int count = 0;
    for(int i=0; i<MAX; i++)
    {
        for(int j=0; j<MAX; j++)
        {
            count+=binaryPartition(a,MAX,MAX,a[i][j]);
        }
    }
    if(count==MAX*MAX)
    {
        cout<<"All Found";
    }
    return 0;
}

March 27, 2012 Posted by | C++ | , , , | Leave a comment

Using Matrix Exponentiation to calculate the Nth Fibonacci Number

Fibonacci numbers have always been interesting since ancient times. The initial puzzle that Fibonacci posed was: how many pairs of rabbits will there be in one year if all of them can mate with each other. There is also a problem on SPOJ related to this.
Now this is the recursive solution. As you can see there are a lot of calls to the function and has exponential time complexity.

int fib(int x)
{
    if (x == 0)
        return 0;

    if (x == 1)
        return 1;

    return fib(x-1)+fib(x-2);
}

Dynamic Programming

The time complexity of this solution is O(n).

int fib(int n)
{
    int a = 1, b = 1,i;
    for (i = 3; i <n;i++)
    {
        int c = a + b;
        a = b;
        b = c;
    }
    return b;
}

Matrix Exponetiation
Now, there is a method to calculate the nth fibonacci number in O(log(n)) time. For this you need the basics of matrix exponentiation. Check out the following matrix

\begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}^n =        \begin{pmatrix} F_{n+1} & F_n \\                        F_n     & F_{n-1} \end{pmatrix}.

The nth fibonacci number can be found using this matrix also if we apply repeated squaring to this matrix, the solution is reduced to O(log(n))

long long fibonacci(int n)
{
    long long fib[2][2]= {{1,1},{1,0}},ret[2][2]= {{1,0},{0,1}},tmp[2][2]= {{0,0},{0,0}};
    int i,j,k;
    while(n)
    {
        if(n&1)
        {
            memset(tmp,0,sizeof tmp);
            for(i=0; i<2; i++) for(j=0; j<2; j++) for(k=0; k<2; k++)
                        tmp[i][j]=(tmp[i][j]+ret[i][k]*fib[k][j]);
            for(i=0; i<2; i++) for(j=0; j<2; j++) ret[i][j]=tmp[i][j];
        }
        memset(tmp,0,sizeof tmp);
        for(i=0; i<2; i++) for(j=0; j<2; j++) for(k=0; k<2; k++)
                    tmp[i][j]=(tmp[i][j]+fib[i][k]*fib[k][j]);
        for(i=0; i<2; i++) for(j=0; j<2; j++) fib[i][j]=tmp[i][j];
        n/=2;
    }
    return (ret[0][1]);
}

July 9, 2011 Posted by | C++ | , , , | 4 Comments