Software Design and Development
Home > Software Design and Development > Core > Software Development Cycle > Standard Algorithms: Searching
Standard search algorithms used in software solutions
This material describes and implements the standard search algorithms required by the syllabus for use in software solutions using pseudocode.
Syllabus outcomes
H4.2 A student applies appropriate development methods to solve software problems.
H4.3 A student applies a modular approach to implement well-structured software solutions and evaluates their effectiveness.
H5.2 A student creates and justifies the need for various types of documentation required for a software solution.
H5.3 A student selects and applies appropriate software to facilitate the design and development of software solutions.
Students must learn to recognise the logic of specified standard approaches, apply those standard approaches as part of the solution to a complex problem and document the logic required to solve a problem using both pseudocode and flowcharts.
The objective of this standard procedure is to determine if a target value is present in an array. Two types of search are specified, one for unsorted arrays, where a linear search is the only option, and one for a sorted array where a binary search is specified in the syllabus.
Linear search
Objective linear search: This requires each element in the array to be read sequentially until the target value is found.
Concept linear search: This algorithm accesses each index position in the array sequentially and compares each element with the target value. If the target value is found a flag is set to true or the index position of the target is returned.
Algorithm linear search
Activity 1: Linear search
- Complete a desk check of the algorithm
LINEARSEARCH
using the following test data and a target
value of 5.
Test data LINEARSEARCH
index
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
element
11
3
12
5
13
4
6
14
7
8
15
1
- Modify the algorithm to return the index position of the target value.
- If there is more than one occurrence of the target value in the array this algorithm would report the first occurrence. How would you modify the algorithm so that it will report the last occurrence of the target value?
Binary search
Objective binary search: This technique requires the sorted array be progressively "chopped" into halves, isolating the target value in the upper, or the lower, half of the array.
Concept binary search: The sorted array is “divided” at the middle index position and the target value is compared to the element in the middle index position, to determine if it is greater than, less than or equal to the element in the middle position. If it is equal then we have found the target. If the target value is less than the element in the middle position then the target is in the lower half of the array. If the target value is greater than the element in the middle position then the target is in the upper half of the array. We ignore that part of the array that does not contain our target value and find the middle index position of that part which does. Compare the target value to the element in the middle position. Is it equal to, less than or greater than the target value? By repeating this procedure we will either find our target or determine it is not present.
Algorithm binary search
Activity 2: Binary search
Desk check the algorithm BINARYSEARCH using the test data below with a target value of 5.
Test data BINARYSEARCH
|
index |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
|
element |
3 |
5 |
12 |
17 |
25 |
33 |
53 |
64 |
72 |
77 |
84 |
86 |
89 |
90 |
99 |
Bibliography
Brookshear, J. Glenn. (1994) Computing Science an overview Fourth Edition, The Benjamin/Cummings Publishing Company.
Stephens, R (1998) Ready-to-Run Visual Basic Algorithms Second Edition,
Wiley Computer Publishing,
Further Resources
Fowler, A (2000) Software Design and Development, First Edition, Heinemann
This work was prepared by
Jennifer Thomson
|