Searching algorithms (linear, binary) in Intro to Computing - Flowchart & Logic Diagram

Process Overview

Searching algorithms help us find a specific item in a list. Linear search checks each item one by one. Binary search splits the list in half repeatedly but needs the list to be sorted.

Flowchart

Set index = 0

↓

index

↓

Increment index by 1

↓

Set low = 0, high = length-1

|Yes↓

Set mid = (low + high) // 2

↓

mid

|No↓

mid

↓

Set high = mid - 1

This flowchart shows two searching methods: linear search checks each item one by one until it finds the target or ends; binary search repeatedly divides a sorted list to find the target faster.

Step-by-Step Trace - 11 Steps

Step 1: Start linear search with list [3, 7, 1, 9] and target 9

Step 2: Check if list[0] == 9

Step 3: Increment index to 1

Step 4: Check if list[1] == 9

Step 5: Increment index to 2

Step 6: Check if list[2] == 9

Step 7: Increment index to 3

Step 8: Check if list[3] == 9

Step 9: Start binary search with sorted list [1, 3, 7, 9, 11] and target 7

Step 10: Calculate mid = (0 + 4) // 2 = 2

Step 11: Check if list[2] == 7

Diagram

List: [1, 3, 7, 9, 11]
Indexes: 0  1  2  3   4

Binary Search Steps:
low=0, high=4
mid=2 -> value=7 (target found)

Linear Search Steps:
Check index 0 -> 1
Check index 1 -> 3
Check index 2 -> 7 (found)

This diagram shows how binary search picks the middle element to check first, while linear search checks each element from the start.

Flowchart Quiz - 3 Questions

Which searching method requires the list to be sorted?

A Both linear and binary search

B Linear search

C Binary search

D Neither linear nor binary search

Key Result

Binary search is faster than linear search but only works on sorted lists, while linear search works on any list by checking items one by one.