We use linear search when looking for a value in an array of limited size. It is a basic concept that is very useful in multiple scenarios as will be shown later.
The Code
In this post, we will show examples in Pseudocode, Python and Java. All 3 examples will use FOR loop to search a small sample array of 6 items.
SET fruits:STRING[6] = ["Apple", "Banana", "Cherry", "Durian", "Pear", "Strawberry"]
DECLARE search AS STRING
PRINT "Enter name of fruit to search"
INPUT search
//linear search code starts here
SET found:BOOLEAN = FALSE
FOR i=0 TO LENGTH(fruits) - 1
IF fruits[i] = search THEN
PRINT search + " found in array"
found = TRUE
BREAK
END IF
NEXT i
IF found = FALSE THEN
PRINT search + " not found"
END IF
fruits = ["Apple", "Banana", "Cherry", "Durian", "Pear", "Strawberry"]
search = input("Enter fruit to search for")
#linear search starts here
found = False
for i in range(len(fruits)):
if fruits[i] == search:
print(search + " found in array")
found = True
break
if not found:
print(search + " not found")
Scanner scn = new Scanner(System.in);
String[] fruits = { "Apple", "Banana", "Cherry", "Durian", "Pear", "Strawberry" };
System.out.println("Enter a fruit to search");
String search = scn.nextLine();
//linear search start here
boolean found = false;
for(int i=0; i <= fruits.length; i++){
if(fruits[i] == search){
System.out.println(search +" found in array");
found = true;
break;
}
}
if(!found){
System.out.println(search +" not found");
}
Key points
SET found:BOOLEAN = FALSE
1) Initializing a boolean variable
Initializing a variable and setting it to False before the start of the for loop is important because its value will change depending on the outcome of the search.
FOR i=0 TO LENGTH(fruits) -1
2) Looping through the array
Create a loop that will loop through every item in the array. A FOR loop or WHILE loop can be used.
IF fruits[i] = search THEN
...
found = TRUE
BREAK
END IF
3) Comparing array item with search value
The IF statement is written in the loop, with the condition to compare the Array item (fruits[i]) with the search value. If the items match, you can print an “Item found” statement or add in any additional codes as required.
found = TRUE
BREAK
These 2 statements are important as the boolean variable has to be changed to True to reflect that the item has been found. “Break” exits the loop as the item has been found and there is no need to continue searching the rest of the array.
IF found = FALSE THEN
...
END IF
4) Condition if item is NOT found
The search value may not exist in the array. Therefore, this IF statement has to be written only after the FOR loop. The “found” variable remaining as False at the end of the FOR loop tells us that the item cannot be found.
Alternatives
if search in fruits:
print(search + " found in fruits")
While the above code is much easier to write, it is still essential to understand the basics of Linear search before using this shorter method.
Example Problem 1
A machine has to undergo a series of tests, and the results of the tests are stored in an array. Any result below 10 means that the machine cannot be used and has to be sent for maintenance. Assume that the results are already stored in an array named “testResults”. Write a program to check if the machine needs to be sent for maintenance or not.
Solution (pseudocode)
SET passed:BOOLEAN = TRUE
FOR i = 0 to LENGTH(testResults) -1
IF testResults[i] < 10 THEN
passed = FALSE
BREAK
END IF
NEXT i
IF passed = TRUE THEN
PRINT "machine passed"
ELSE
PRINT "machine failed"
END IF
Example Problem 2
At a party, the children are split into groups of 4 to play a game. The requirement is that every group must have at least 1 girl and 1 boy. The group composition is written as a string – “GGBB” represents 2 girls and 2 boys in 1 group. A array named “partyGroups” contains all the strings of the group compositions. Your task is to print the indexes of the groups that do not meet the criteria. Do note it is possible that a group can have less than 4 children.
Solution (python)
invalidGroups = []
for i in range(len(partyGroups)):
#initialize 2 variables to count number of boys and girls in a group
girlCount = 0
boyCount = 0
#check each letter in the string
for letter in partyGroups[i]:
if letter == "G":
girlCount += 1
elif letter == "B":
boyCount += 1
#inner for loop completed. Check boyCount and girlCount
if boyCount < 1 or girlCount < 1:
invalidGroups.append(i) #append index of group
#print out index numbers
if len(invalidGroups) > 0:
print("Index numbers of invalid groups:", end=" ")
for item in invalidGroups:
print(item, end=",")
print()
else:
print("There are no invalid groups")
As you can see, Example problem 2 is slightly more complicated than Problem 1, but still utilizes the basic principle of having a variable before the start of the FOR loop to keep track of the items in the array that fail the condition. Many programming scenarios require searching an array of values, so by understanding the Linear search algorithm, you will be able to tackle these problems easily.