Min/Max/Search in circular array

/* Problem: An array is shifted N times, so we get a circular shifted array.
 * 1. Search for a number in an efficient way
 * 2. Find the start index ie. MIN element in the array
 * 3. Find the   end index ie. MAX element in the array
 */

#include<iostream.h>

int array[] = { 7,8,9,0,1,2,3,4,5,6};
#define SIZE sizeof(array)/sizeof(array[0])

void search(int key)
{
    int left = 0;
    int right = SIZE;
    int mid;
    while(left<right)
    {
        if(right-left == 1)
        {
            if(array[left] == key)
                cout<<"Match found\n";
            else if(array[right] == key)
                cout<<"Match found\n";
            else
                cout<<"Match not found\n";
            break;
        }
        mid = (right-left)/2 + left;

        if(array[mid] == key)
        {
            cout<<"Key found: "<<key<<endl;
            break;
        }
        if(array[left] <= array[mid])
        {
            // sub case #1
            if(key >= array[mid] && array[right]>=key)
            {
                left = mid;
            }
            else
                right = mid;
        }
        else
        {
            // right sub arrary is sorted
            if(key >= array[mid] && key <= array[right])
                left = mid;
            else
                right = mid;
        }
    }

}
void findMax()
{
    int left = 0;
    int right = SIZE - 1;
    int mid;

    while(left<right)
    {
        mid = (right-left) /2 + left;
        if(right-left == 1) {
            cout<<"Max :"<< (array[right] > array[left] ? array[right]:array[left])<<endl;
            return;
        }
        if(array[mid] > array[left] && array[mid] > array[right])
            left = mid;
        else if(array[mid] < array[left] && array[mid] < array[right])
            right = mid;
        else
            left = mid;
    }

    cout<<"Max element: "<<array[mid] <<" "<<array[left]<<" "<<array[right]<<endl;
    return;
}

void findMin()
{
    int l = 0;
    int r = SIZE -1;
    int m;

    while(l<r)
    {
        m = (r-l)/2+l;
        if(r-l == 1)
        {
            cout<<"Min: "<<(array[r]<array[l] ? array[r]:array[l])<<"\n";
            return;
        }
        if (array[l]  > array[m] && array[r] > array[m])
            r = m;
        else if(array[l] < array[m] && array[r] < array[m])
            l =  m;
        else
            r = m;
    }
    cout<<"Minimum: "<<array[m]<<"\n";
}
int main()
{
    cout<<"Enter the no you want to search!! ";
    int key;
    cin>>key;

    search(key);
    findMax();
    findMin();
    return 0;
}

Advertisement

~ by Ganesh on December 31, 2008.