Time efficient algorithm.

Question

Write a time efficient algorithm to find the ith maximum and ith minimum number from the

reverse sorted array.

Answer 1

ASSUMING the array has ZER0 BASED Indexing and ASSUMING all of the data

is UNIQUE, then there is no algorithm necessary...

The kth largest element shall be at A[K-1] and hte kth smallest element shall be

at A[N-k]

Otherwise, I would suggest a linear search for K-1 times the data changes.

I suppose a modified BINARY search is possible, where each sampling of

the array checks the neighbor below and above for changes in the data before

each recursive call...

Here is an implementation of the linear search

using namespace std;

#include <iostream>

// posK>1 retrieves the Kth greatest

// posK<1 retrieves the Kth smallest

// returns 0 on success, -1 on failure

int LinearSearch( int * A, int N, int posK, int * iResult)

{

int iReturn = -1;

*iResult=-1;

if (posK!=0)

{

int iStartIndexPos = (posK>0) ? 0 : N-1;

int iStopIndexPos = (posK>0) ? N-1 : 0;

int numDataChanges = (posK>0) ? posK-1 : -posK-1 ;

bool switch_flag = posK>0;

cout << iStartIndexPos << " " << iStopIndexPos << " " << numDataChanges << endl;

int iLoop=iStartIndexPos;

int curData = A[iStartIndexPos];

while (iLoop!=iStopIndexPos)

{

if (curData==A[iLoop])

{

}

else

{

numDataChanges--;

}

curData = A[iLoop];

iLoop = (switch_flag) ? iLoop+1 : iLoop-1;

if (numDataChanges==0) { break; }

cout << "iLoop=" << iLoop << endl;

cout << "# of data changes " << numDataChanges << endl;

}

//loop stopped because # of data changes has occurred

if (numDataChanges==0)

{

*iResult=curData; //records the results

iReturn=0;

}

}

return(iReturn);

}

int main()

{

int A[] = {10,10,10,9,9,9,9,8,8,7,7,7,7,6,6,6,5,5,5,5,4,4,4,4,4,3,3,3,3,2,2,2,2,1,1,1};

int iResult=-1;

int iReturn = LinearSearch(A,36,4,&iResult);

if (iReturn>-1)

{

cout << iResult << endl;

}

else

{

cout << " NOT FOUND " << endl;

}

}