header
Binary Search on Sorted Array

Tag:
Edit edit   Starstar   Delete   Add Picture

Program Information

Name: Binary Search on Sorted Array
Domain: Algorithm
Functionality: Perform binary search on a sorted array
Input: N: Target element to be found (Type: Integer) A[1…k]: The given sorted array with k 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

Automated Metamorphic Testing http://dx.doi.org/10.1109/CMPSAC.2003.1245319
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, As[1…k]>
Source output: IDs
Follow-up input: <Nf, Af[1…k]>
Follow-up output: IDf
Input relation: When IDs = -1, let Af[1…k] = As[1…k] and Nf = Af[p] where 1<=p<=k.
Output relation: IDf = p.
Pattern:

MR2------

Description:
Property:
Source input: <Ns, As[1…k]>
Source output: IDs
Follow-up input: <Nf, Af[1…k]>
Follow-up output: IDf
Input relation: When IDs = k, As[k-1] < Ns < As[k+1], let Af[1…k] = As[1…k] and As[k-1] < Nf < As[k+1] and Nf != Ns
Output relation: IDf = -1.
Pattern:

MR3------

Description:
Property:
Source input: <Ns, As[1…k]>
Source output: IDs
Follow-up input: <Nf1, Af1[1…k]>
Follow-up output: IDf1
Input relation: When IDs = k, As[k-1] < Ns < As[k+1], let Af1[1…k] = As[1…k] and Af2[1…k] = As[1…k], and Nf1 = As[k-1], Nf2 = As[k+1]
Output relation: IDf1 = k-1, IDf2 = k+1
Pattern:

MR4------

Description:
Property:
Source input: <Ns, As[1…k]>
Source output: IDs
Follow-up input: <Nf, Af[1…k]>
Follow-up output: IDf
Input relation: Nf = F(Ns), Af[i] = F(As[i]), i = 1…k, F is any increacing function over N*
Output relation: IDf = IDs
Pattern:
Insert title here