header

Binary Search on Sorted Array : Perform binary search on a sorted array
Tag:
Edit edit   Starstar

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


    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.

MR2


    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.

MR3


    Source input: <Ns, As[1…k]> ; Source output: IDs
    Follow-up input: <Nf1, Af1[1…k]> ; Follow-up output: IDf1
    Follow-up input: <Nf2, Af2[1…k]> ; Follow-up output: IDf2
    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

MR4


    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

Related

Insert title here