Embedded Files
Search Algorithms
Search Algorithms
An algorithm is a sequence of instructions to solve a given problem. Common methods of defining algorithms include pseudo-code, flowcharts and structured English.
Two different types of search algorithm are linear search and binary search.
Here is an overview of both a Linear & Binary Search
Here is an overview of both a Linear & Binary Search
Linear Search Algorithm
Linear Search Algorithm
Examine each element in the list (in order) until the appropriate one is found
Why use a Linear Search?
When the number of items to be searched is very small
When the search value is one of the first items in the Search Array
3. Can be used on an unsorted list
Linear Search Algorithm
Declare SearchArray(10) As Integer
Declare Found As Boolean
Output “Please enter SearchValue”
Input SearchValue
Found = False
For count = 1 to 10
If SearchValue = SearchArray(Count) then
Output “The Search Value has been found at position: “ , count
Found = True
End If
EndLoop
If Found = False then
Output “Search Value not found.”
End If
See WJEC knowledge organiser for alternative to this algorithm.
Examiner Tips:
Examiner Tips:
Examiners are looking for the following when you write an algorithm.
Declare and initialise variables
Input searchValue
Loop structure and increment
Determine position if found
Output position if found
Correct terminating condition for loop
Output message if not found
Algorithm works as intended.
Sample Question:
Binary Search Algorithm
Binary Search Algorithm
Data must be pre-sorted before search begins
•Examine median number in list (middle position in list)
•Depending on value of median number, either search left hand sub-list or right-hand sub-list, getting rid of the opposite half of the list (uses recursion i.e. algorithm calls itself)
Why use a Binary Search?
More efficient (quicker) than a linear search
Can be used when the number of data items is large
Binary Search Algorithm
Find middle (median) number in list
Compare middle (median) number with required number
IF match found
STOP search
ELSE
IF required number is less than middle number
Get rid of upper half of list
Search lower half list (restart algorithm)
ELSE
Get rid of lower half of list
Search upper half list (restart algorithm)
ENDIF
ENDIF
See WJEC knowledge organiser for alternative to this algorithm.
Examiner Tips:
Examiner Tips:
Examiners are looking for the following when you write an algorithm.
Declare and initialise variables
Input SearchValue
Loop structure and increment
Determine new position of start of list
Determine new position of end of list
Output position if found
Correct terminating condition for loop
Output message if not found
Algorithm works as intended.
Sample Question:
Sample Answer:
It is possible to show diagrammatically how the algorithm will reduce the part of the array being searched at each repetition.
Image A below shows the Array before any repetitions are carried out.
Image B below shows how the algorithm will reduce the part of the array being searched at each repetition. This is indicated by the discarded elements being crossed out or shaded.
Image A
Image A
Image B
Image B
Test Data
Test Data
Sort Algorithms - Duplicate values, accending order, decending order, negative numbers
Searching Algorithms - test with value in array, test with value not in the array, dulicate values, test at boundaries
Useful links:
Useful links:
A Binary search can be programmed iteratively or recursively.
Find out more here:
https://www.geeksforgeeks.org/linear-search/
https://www.geeksforgeeks.org/binary-search/
https://resource.download.wjec.co.uk/vtc/2020-21/ko20-21_1-4/wjec_ko_as_9-4.pdf
Page updated
Report abuse