header
kth Occurrence of x in Unsorted Array

Tag:
Edit edit   Starstar   Delete   Add Picture

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------

Description:
Property:
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
Pattern:

MR2------

Description:
Property:
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
Pattern:

MR3------

Description:
Property:
Source input: <Ns, Ks, As[1…ms]>
Source output: IDs
Follow-up input: <Nf1, Kf1, Af1[1…mf1]>
Follow-up output: IDf1
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
Pattern:
Insert title here