Search Algorithms

Search Algorithms

1 / 20
volgende
Slide 1: Slide
newEditor

In deze les zitten 20 slides, met tekstslides.

Dit is niet oké

Onderdelen in deze les

Search Algorithms

Learning Objective

  • To describe the purpose and real-life applications of search algorithms, with a focus on linear search.

  • To understand and explain how the linear search algorithm works by scanning through items sequentially.

    Success Criteria
    1.Debug and analyse linear search programs to ensure accurate and efficient target identification;
    2. Evaluate the algorithmic efficiency of linear search in terms of best, worst, and average case scenarios;
    3. Apply linear search logic in solving real-world challenges, such as inventory checking and counting occurrences in lists.

2

Pre-Assessment

1. What is the main purpose of a search algorithm?

A. To sort data into alphabetical order B. To find a specific item within a collection of data

C. To delete unwanted items from a list D. To convert data into binary

2. Which statement best describes linear search?

A. It only works on sorted lists B. It checks items in random order

C. It scans each item one by one until the target is found D. It divides the list into halves repeatedly

3. In the linear search pseudocode, what does the variable index represent?

A. The number of times the loop runs B. The position of the current item being checked

C. The total number of items in the list D. The target value

4. When does the linear search algorithm stop checking items?

A. When the list is sorted B. When index becomes greater than or equal to size C. When the user enters a new target D. When the list contains only one item

5. What does the program display if the target number is not found in the list?

A. Search complete B. Try again C. Item not found D. Error



Pre-Assessment-Answer

1. What is the main purpose of a search algorithm?

A. To sort data into alphabetical order B. To find a specific item within a collection of data

C. To delete unwanted items from a list D. To convert data into binary

2. Which statement best describes linear search?

A. It only works on sorted lists B. It checks items in random order

C. It scans each item one by one until the target is found D. It divides the list into halves repeatedly

3. In the linear search pseudocode, what does the variable index represent?

A. The number of times the loop runs B. The position of the current item being checked

C. The total number of items in the list D. The target value

4. When does the linear search algorithm stop checking items?

A. When the list is sorted B. When index becomes greater than or equal to size C. When the user enters a new target D. When the list contains only one item

5. What does the program display if the target number is not found in the list?

A. Search complete B. Try again C. Item not found D. Error



Starter:

Searching for words in a puzzle is a great way to understand how we recognise patterns and organise information.

Imagine being given a grid filled with random letters. Hidden within the grid are specific words and your task is to find them.

To solve the puzzle, you carefully scan through the letters, looking for patterns that match the words you are searching for. This is similar to how we search specific items in a list while programming.

5

Starter:

6

Introduction

7

Search algorithms are tools that help us find specific items in a group of data. They are used in everyday tasks like searching for a file on a computer, looking for information on the internet, or finding a product in an online store.

Introduction

8

A search algorithm works by following steps to find the item you need. The method used varies depending on how the data is organised. Ordered data requires an approach different from data organised randomly.

9

Linear search -video


To learn about Linear search, scan the QR code or open the link.

https://go.qubitscs.com/Iwmxs

Linear search

10

Linear search, also known as sequential search, is a method for finding an item in a list. It works like searching for a book on a shelf. You start from one end and examine each book until you find the right one. Irrespective of the order, each item is checked one by one until the correct one is found.


Linear search

11

Let’s take an example with a list of numbers, as shown in the image. If the target item is 20, we search for it from the beginning of the list by comparing each item.

Thus, linear search works by going through each item one by one until the one you are looking for is found.

Algorithm and pseudocode for linear search

12

Pseudocode using conditional statements

The linear search algorithm uses loop and conditional statements to check for an item in a list. The pseudocode for these statements is as follows:

Algorithm

Pseudocode

IF condition THEN if_block_statement

ELSE else_block_statement

IF (condition)

{

<IF block statement>

}

ELSE

{

<ELSE block statement>

}


Algorithm and pseudocode for linear search

13

Pseudocode using conditional statements

The linear search algorithm uses loop and conditional statements to check for an item in a list. The pseudocode for these statements is as follows:

Algorithm

Pseudocode

REPEAT steps UNTIL condition

REPEAT UNTIL (condition)

{

<block of statement>

}


Algorithm and pseudocode for linear search

14

Let’s write an algorithm and its corresponding pseudocode to perform the linear search on a list of items. Here, the algorithm takes a list from the user and a target item to search in the list. The loop iterates through the list, and conditional statements check whether the target item is present in the list or not.


Algorithm and pseudocode for linear search

15

Algorithm

Pseudocode

Step 1: Prompt the user to enter the length of the list and store it in size.


Step 2: Prompt the user to enter a list and store it in the list.


Step 3: Prompt the user to enter the target item and store it in target.


Step 4: Set the value of the index as 0.


Step 5: Set the value of found to false.

Algorithm and pseudocode for linear search

16

Algorithm

Pseudocode

Step 6: IF the list item at index is equal to target, THEN update found as true and display Item found.


Step 7: Update index as index + 1.


Step 8: Repeat steps 6 and 7 until index becomes greater than or equal to size.


Step 9: IF found is equal to false, display Item not found.

AFL: Linear search

17

Answer the following questions based on the algorithm and pseudocode given above:

  1. What inputs are needed for the linear search algorithm?

  2. When does the program stop searching for the target number?

  3. What should the program display if the target number is not in the list?

AFL: Linear search - Solution

18

  1. Input needed for the linear search algorithm:

  • The length of the list (size)

  • The list of numbers (list)

  • The target number to search for (target)

  1. The program starts searching for the target item:

    1. By comparing the target item with each list item

    2. If the item is present in the list, it displays Item found

AFL: Linear search - Solution

19

  1. The program stops searching for the target number

when the index becomes greater than the size of the list.

  1. The program displays the following text if the target number is not in the list:

Item not found

Sorting Out

20

Challenge 1:

A list contains 10 items. The target is located at the 10th position. Explain whether this represents the best, average, or worst case for linear search and justify your answer.

Challenge 2:

You are designing a system for checking whether a product is in a warehouse inventory list. Explain why linear search may or may not be efficient for this task, and suggest one improvement that could make searching faster.