header

kth Occurrence of x in Unsorted Array : locate the kth occurrence of a key from an unsorted array
Tag:
Edit edit   Starstar

Program Information

Name: kth Occurrence of x in Unsorted Array
Domain: Algorithm
Functionality: locate the kth occurrence of a key from an unsorted array
Input:
     N: Target element to be found (Type: Integer) K: Find Kth occurrence of target(Type: Integer) A[1…m]: The given array with m elements (Type: Array of distinct integers)
Output:
     ID: location of the found element in A[], ID>= 0 if found, ID=-1 otherwise (Type: integer)

Reference

         Metamorphic Testing: A New Approach for Generating Next Test Cases http://www.cse.ust.hk/~scc/publ/CS98-01-metamorphictesting.pdf

MR Information


MR1


    Source input: <Ns, Ks, As[1…ms]> ; Source output: IDs
    Follow-up input: <Nf, Kf, Af[1…mf]> ; Follow-up output: IDf
    Input relation: When IDs = -1, let Af[1…mf] = As[1…ms] and Nf = As[r], Kf = 1
    Output relation: IDf <= r and IDf != -1

MR2


    Source input: <Ns, Ks, As[1…ms]> ; Source output: IDs
    Follow-up input: <Nf, Kf, Af[1…mf]> ; Follow-up output: IDf
    Input relation: When IDs = p, Ns = As[p], let Nf = Ns, Kf = 1 and Af[1…mf] = As[p…ms] or As[p..p]
    Output relation: IDf = IDs

MR3


    Source input: <Ns, Ks, As[1…ms]> ; Source output: IDs
    Follow-up input: <Nf1, Kf1, Af1[1…mf1]> ; Follow-up output: IDf1
    Follow-up input: <Nf2, Kf2, Af2[1…mf2]> ; Follow-up output: IDf2
    Input relation: When IDs = p, Ns = As[p], let Nf1 != Ns, As[p-1], As[p+1], Kf1 = 1 and Af1[1…mf] = As[p-1…p+1] or As[p..p]; Nf2 = Ns, Kf2 = 2, Af2[1…mf2] = As[r-1…ms];
    Output relation: IDf1 = -1; IDf2 = -1 or m where m > r

Related

Insert title here