header
Search Program 

Tag:
Edit edit   Starstar

Program Information

Name: Search Program 
Domain: Algorithm
Functionality: searches for an integer in an ordered data structure T 
Input: An input integer x is the test value used in the search, a set of integers sorted in ascending order T 
Output: -1 if x is not found, or when x is found, the program returns the starting and ending positions of x in T that is represented in the form of ($y_{1}$, $y_{2}$) 

Reference

 Metamorphic Testing and Testing with Special Values
https://pdfs.semanticscholar.org/b52d/60d4e2b50d6d244b1bb1a7e2db9829046db5.pdf?_ga=2.57987562.1914929612.1565157787-500444029.1561960669  

MR Information

MR1------

Description: the search function f, T is an ordered list containing integers in ascending order , $y_{1}$ is the starting position of $x_{1}$ and $y_{2}$ is the ending position of $x_{1}$ or $y_{1}$ = -1 if $x_{1} \notin T$, $y_{3}$ is the starting position of $x_{2}$ and $y_{4}$ is the ending position of $x_{2}$ or $y_{3}$ = -1 if $x_{2} \notin T$ 
Property: $$\forall x_{1} \in T : f(x_{1}, T)  = (y_{1}, y_{2}) , \forall x_{2} = x_{1} + 1 \in T : f(x_{2}, T)  = (y_{3}, y_{4}) , then  (y_{1} = -1) \vee (y_{3} = -1) \vee ((y_{2} + 1) = y_{3}) $$ 
Source input:
Source output:
Follow-up input:
Follow-up output:
Input relation:
Output relation:
Pattern:

MR2------

Description: the search function f, T is an ordered list containing integers in ascending order , $y_{1}$ is the starting position of $x_{1}$ and $y_{2}$ is the ending position of $x_{1}$ or $y_{1}$ = -1 if $x_{1} \notin T$, $y_{3}$ is the starting position of $x_{2}$ and $y_{4}$ is the ending position of $x_{2}$ or $y_{2}$ = -1 if $x_{2} \notin T$, T’ is $ \{ z \} \cup T$ where z < head (T) and head(T) denotes the first element of T 
Property: $$\forall x \in T : f(x, T)  = (y_{1}, y_{2}), \forall x \in T’ and x \neq z : f (x, T’) = (y_{3}, y_{4}) , then (y_{1} = y_{3} = -1) \vee ((y_{3} = y_{1} + 1) \wedge  (y_{4} = y_{2} + 1))$$ 
Source input:
Source output:
Follow-up input:
Follow-up output:
Input relation:
Output relation:
Pattern:
Insert title here