Next Lesson

ICS4U – Python Search Algorithms

ICS4U Grade 12 Computer Science ICS4U – Python Search Algorithms

ICS4U Learning Goals

In this ICS4U Grade 12 Computer Science lesson you will be learning how to

Implement a Sequential Search Algorithm
Implement a Binary Search Algorithm
Solve a 2D maze using recursion

Search Algorithms

Suppose you have a list of data and you want to find the location of a “target” value in that list

Sequential Search Algorithm

This is pretty basic algorithm, you have already been using to find data in a list.

The algorithm works as follows:

Start with the first value in the list
Compare it to the target value
- If its the same, return current index
- If its not the same then move to the next value in the list

If the target appeared multiple times, then this algorithm would only return the location of the first occurrence of the target

				
					#a is the list to search through
#target is the value being searched for
#Returns the index of the first occurence of target
#Returns -1 if the target is not found
def sequentialSearch(a, target):
	for i in range(0,len(a)):
		if target == a[i]:
			return i
	return -1

If you wanted to test that program you could write a main method that might look something like this

				
					#Test Program
def main():

	myList = [3,7,7,4,2,3,8,19,20,4,8,33,2,1]

	lookFor = int(input("Find what number? "))

	foundAt = sequentialSearch(myList,lookFor)

	if foundAt != -1:
		print(lookFor, "was found at index:",foundAt)
	else:
		print(lookFor, "was not found in the list")

main()

Binary Search Algorithm

Now if the elements of the list we are searching through are already sorted in ascending or descending order, then a Binary Search Algorithm could be used instead.

The Binary Search is a divide and conquer technique. Each step of the search proceeds as follows (Assume the list is in ascending order)

Examine the value in the middle of the list
- If the target is smaller than the value in the middle then discard the right half of the list (No point searching it because it isn’t there)
- If the target is larger than the value in the middle then discard the left half of the list (no point searching it because it isn’t there)
Repeat this process until eventually the only value left to look at will be in the middle of the list and that must be the target. If eventually that middle value isn’t the target, then target isn’t in the list

Key point with this algorithm, is that the list MUST be already sorted

				
					#a is the list to search through
#target is the value being searched for
#Returns the index of the last occurence of target
#Returns -1 if the target is not found
def binarySearch(a, target):

	#Look at the list between first and last index values
	first = 0
	last = len(a) - 1

	while first <= last:

		#Middle of the current portion being looked at (index must be int)
		mid = (first + last) // 2

		#Discard right half by setting new last
		if target < a[mid]:
			last = mid - 1

		#Discard left half by setting new first
		elif target > a[mid]:
			first = mid + 1

		#Found target
		else:
			return mid

	#Only gets here if target wasn't found
	return -1

If you wanted to test that program you could write a main method that might look something like this

				
					#Test Program
def main():

	myList = [1,3,3,4,7,9,11,17,22,30,46,70,70,82]

	lookFor = int(input("Find what number? "))

	foundAt = binarySearch(myList,lookFor)

	if foundAt != -1:
		print(lookFor, "was found at index:",foundAt)
	else:
		print(lookFor, "was not found in the list")

main()

ICS4U Interactive Learning Activity - Grade 12 Computer Science

You should watch these algorithms search in a simulation. Visit the following website and you can choose to see how the Sequential Search Algorithm works, or how the Binary Search Algorithm works.

Searching Simulation

2D Maze Search

A useful programming tool is learning how to write an algorithm that searches for a solution to a maze. (That is to find a path from a starting point in the maze to an ending point in a maze)

There are a lot of different algorithms that can be used to explore mazes

Depth First Search
Breadth First Search
Dijkstra’s Search Algorithm
A* Search Algorithm

These are generally a bit complex for this course but we can write our own fairly straightforward algorithm to accomplish that task. It doesn’t find the optimal (Shortest) path but it will find “a” solution to the maze.

The optimal way to write these maze finding algorithms is to use recursion. The algorithm is a bit hard to explain over text, so I will attempt to demonstrate it over video

Here is the complete code from the video. Just remember that I’m using a clear screen command from Windows to make my simulation look better. That needs to be run from a terminal to work correctly.

				
					import os, time, random

#2D list of the maze layout
maze = []

#2D list of the path taken [row,col] coordinates
path = []


#Print maze
def displayMaze():
    
    #Slow down to watch simulation
    time.sleep(0.2)
    os.system("cls")
 
    #Adjust output to make it look better on the screen
    map = "\n\n"
    for row in range(0,len(maze)):
        for col in range(0,len(maze[row])):
            if maze[row][col] == "1":
                map = map + "[X]"

            if maze[row][col] == "0":
                map = map +  "   "

            if maze[row][col] == ".":
                map = map + " . "

            if maze[row][col] == "2":
                map = map + "   "

            if maze[row][col] == "E":
                map = map + " E "

            if maze[row][col] == "S":
                map = map + " S "
            
        map = map + "\n"
   
    print(map)

#Move through the maze
def move(row,col):
    
    global path
    global maze
    
    
    #Possible Movements
    possibles = [[row,col+1],[row,col-1],[row-1,col],[row+1,col]]

    #Randomize direction choice so it doesn't favor 1 direction over another
    random.shuffle(possibles)

    
    #Move along the open paths
    if maze[row][col] == "0" or maze[row][col] == "S":

        #Mark path as open 
        maze[row][col] = "."
        path.append([row,col])
        displayMaze()

        #Move in next possible direction
        if (move(possibles[0][0],possibles[0][1])):
            return True

        elif (move(possibles[1][0],possibles[1][1])):
            return True
        
        elif (move(possibles[2][0],possibles[2][1])):
            return True
        
        elif (move(possibles[3][0],possibles[3][1])):
            return True
        
        #Mark path as dead end and backtrack
        else:
            maze[row][col] = "2"
            path.remove([row,col])
            displayMaze()
            return False

    #Found exit  
    elif maze[row][col] == "E":
        maze[row][col] = "."
        path.append([row,col])
        return True
    
    return False

def main():
    os.system("cls")

    # Store the maze in a 2D list
    global maze
    file = open("MazeSearchFile.txt", "r")
    while True:
        line = file.readline()
        if line == "":
            break
        else:
            values = line.rstrip("\n").split(",")
            maze.append(values)

    #Find the starting position
    for row in range(0,len(maze)):
        for col in range(0,len(maze[row])):
            if maze[row][col] == "S":
                startRow = row
                startCol = col
                break
    
    #Make the first move
    move(startRow,startCol)
    
    #Maze Solved
    displayMaze()
    print("A Solution:")
    print(path)

#Start the program
main()

ICS4U Coding Questions

Try to code the following questions using an IDE of your choice. You will save those files on your computer for future reference.

Each question has:

A video of your teacher live coding and explaining the solution
The final code used in the video.

Try your best to solve the problems yourself without looking at the solutions.

Make sure you test your programs with multiple different inputs to ensure it is functioning properly.

Treat these questions like Math homework (Do as many as you feel you need to do to feel comfortable with the material)

ICS4U Practice Question

Name Your File: “ICS4UsequentialMod.py”

Write a couple of new functions for the sequential search algorithm so that it will return

the last occurrence of the target in the list
all the target locations in the list (return a list of the target locations)

Solution

				
					def sequentialSearchLast(a, target):
	last = -1
	for i in range(0,len(a)):
		if target == a[i]:
			last = i
	return last

def sequentialSearchAll(a,target):
	locations = []
	for i in range(0,len(a)):
		if target == a[i]:
			locations.append(i)
	return locations

ICS4U Practice Question

Explore Maze Searching

Make your own maze to test the recursive maze program.
- Make sure your maze has multiple ways to get to the end
Each time the program runs, it finds a different solution to the maze by exploring a different path.
- Run your program several times and each time have it count how many moves it takes to get to the end.
- Append that data to a text file after each run of the program.
Write a secondary program that will display the average, max, and min number of steps needed to find the solution to your maze

Solution

#Working on it

Previous Lesson

Back to Course

Next Lesson