Tutorial 1

🔎

Linear Search

2210 O-Level

i

It may be useful to search (CTRL + F) for "linear search" questions in the (combined) past papers

1

Linear Search

Often we want to search to see whether a specific value exists in an array - we can use linear search to do that:

  1. Initialise an index variable to point to first element in array
  2. Loop through array element-by-element
  3. If current element is the value we are searching for, then update flag/return TRUE if in a function etc
  4. If item hasn't been found after looping through all elements in the array, then we know the item doesn't exist
DECLARE nums : ARRAY[1:5] OF INTEGER DECLARE targetNumber, index : INTEGER DECLARE found : BOOLEAN nums[1] <-- 6 nums[2] <-- 3 nums[3] <-- 8 nums[4] <-- 2 nums[5] <-- 5 OUTPUT "Enter number to search for:" INPUT targetNumber index <-- 1 found <-- FALSE //loop to 5, since 5 elements in array WHILE found = FALSE AND index <= 5 DO IF nums[index] = targetNumber THEN found <-- TRUE ENDIF index <-- index + 1 ENDWHILE IF found = TRUE THEN OUTPUT targetNumber, " is in the array!" ELSE OUTPUT targetNumber, " is not in the array!" ENDIF

2

Function Version

Note: we can also write this as a function, returning TRUE if we find the item, while returning FALSE is we have looped through the entire array and not found the item

DECLARE nums : ARRAY[1:5] OF INTEGER DECLARE targetNumber : INTEGER nums[1] <-- 6 nums[2] <-- 3 nums[3] <-- 8 nums[4] <-- 2 nums[5] <-- 5 OUTPUT "Enter number to search for:" INPUT targetNumber IF LinearSearch(nums, targetNumber) = TRUE THEN OUTPUT targetNumber, " is in the array!" ELSE OUTPUT targetNumber, " is not in the array!" ENDIF FUNCTION LinearSearch(arr : ARRAY OF INTEGER, toFind : INTEGER) RETURNS BOOLEAN DECLARE index : INTEGER FOR index <-- 1 TO 5 IF arr[index] = toFind THEN RETURN TRUE ENDIF NEXT index RETURN FALSE ENDFUNCTION