p. 419 · PDF 429

2 - 2 Data Search Process

The process of finding the target data from the recorded data is called search. Representative search algorithms are linear search and binary search.

2-2-1 Linear Search

Linear search (sequential search) is the algorithm that searches for the target value in sequence from the first element. A liner search algorithm that searches for the input target value X from array T is considered. The array T has N elements where data is recorded and returns the position (i.e., index) where the target value X is recorded. When an element that matches with the target value X does not exist, “–1” is returned instead of the index.

Enlarge original visual

Original source text

1 
2 
3 
··· 
N 
T 
35 
67 
21 
··· 
54
X
··· Enter during the process 

Source visual description

Original Data Search Process source layout. Source labels: 1; 2; 3; ···; N.

In linear search, comparison is made in sequence from the first element T(1) to T(N), in order to determine whether the element matches with the target value X or not. Therefore, in Figure 7-20, the algorithm searches for the element for which “T(I)=X” while index I is changed in sequence from 1 to N. (Condition “I > N” holds true when there is no element in T(1) through T(N) that matches with X.) However, Figure 7-20 is not a combination of basic structures: that is, exit of iteration is at two places. Therefore, this algorithm is rewritten in Figure 7-21.

p. 420 · PDF 430

Enlarge original visual

Original source text

Figure 7-20  Linear search (1) 
Figure 7-21  Linear search (2) 

Source visual description

The original linear-search charts retain the end-of-range and match tests, the index increments and the returns of I or minus one.

In Figure 7-20 and Figure 7-21, two conditions of “I > N” and “T(I) = X” are compared for every one round of iteration. There is a concept called sentinel method that reduces this comparison of conditions (i.e., decision process) and improves process efficiency. In the sentinel method, prior to searching, in the last of all elements, the target value is stored as “sentry”. If “sentry” is stored, the target value is always found. Therefore, it is sufficient to just keep the ending condition of iteration as “‘T(I) = X’ where the target value is found”. Figure 7-22 shows the algorithm of the sentry method that uses the following array T.

Enlarge original visual

Original source text

1 
2 
3 
··· 
N 
N+1
T 
35 
67 
21 
··· 
54
··· T(N+1): Element where sentry is stored 

Source visual description

Original Data Search Process source layout. Source labels: 1; 2; 3; ···; N.

In addition, linear search can also be used in the list. When a list is used, elements are searched for in sequence while the list is traced by using a pointer from the first element. In Figure 7-23, an algorithm searches for the entered target value X from the data that is recorded in the list using the following array, and returns the position (i.e., index) where the data is recorded.

Enlarge original visual

Source visual description

Original Data Search Process source layout. Source labels: .

p. 421 · PDF 431

Enlarge original visual

Original source text

Figure 7-23  Linear search (list) 
Figure 7-22  Linear search  
(sentinel method) 

Source visual description

The original sentinel linear-search flowchart places X in T(N+1), performs the comparisons and checks the original range before returning. The original list-search flowchart starts at HEAD, compares D(I) with X and follows PT(I).