Saturday, December 10, 2011

Search an element in sorted rotated array

int binarySearch(int arr[], unsigned int low, unsigned int high, int key)
{
    if( low == high && arr[low] != key)
    {
       return -1;
    }

    unsigned int mid = low + (high - low)/2;

    if(key == arr[mid])
    {
       return mid;
    }  
    else if (key > arr[mid])
    {
       return binarySearch(arr, mid + 1, high, key);
    }
    else
    {
       return binarySearch(arr, low, mid - 1, key);
    }
}


int search(int arr[], unsigned int low, unsigned int high, int key)
{
    if( low == high && arr[low] != key)
    {
       return -1;
    }

    unsigned int mid = low + (high - low)/2;

    if(key == arr[mid])
    {
       return mid;
    }
    else if(arr[mid] < arr[low]) // That means that the right half may be sorted
    {
       if((key > arr[mid]) && (key <= arr[high]))
       {
           return binarySearch(arr, mid + 1, high, key);  //Here we know we just need to look
                                                                               //into sorted part of array
       }
       else
       {
           return search(arr, low, mid-1, key);
       }
    }
    else // That means that the Left half may be sorted
    {
       if((key >= arr[low]) && (key < arr[mid]))
       {
           return binarySearch(arr, low, mid - 1, key);  //Here we know we just need to look
                                                                              //into sorted part of array
       }
       else
       {
           return search(arr, mid + 1, high, key);
       }
    }
}

1 comment:

  1. thanks for the share..
    good one.. :)
    keep posting :)

    ReplyDelete