Lesson 17 • Advanced

Searching Algorithms

30 minutes

Algorithms

What is Searching?

Searching is the process of finding a specific element in a collection of data. It's one of the most common operations in programming - from finding contacts in your phone to searching for products online.

Why Searching Matters

Efficient searching is crucial for:

Speed: Finding data quickly in large datasets
User Experience: Fast search results
Performance: Better algorithms = faster programs
Real-world apps: Every app needs search functionality

📏 Linear Search

Linear Search checks every element one by one until it finds the target or reaches the end. It's simple but can be slow for large datasets.

How it Works:

Start at the first element
Check if it matches what we're looking for
If yes, return the position
If no, move to next element
Repeat until found or end of array

Example: Linear Search

Algorithm LinearSearch

var numbers = [23, 45, 12, 67, 89, 34, 56]
var target = Input "Enter number to search:"

var found = false
var position = -1

# Search through array
For i = 0 To Size(numbers) - 1
    If numbers[i] == target Then
        found = true
        position = i
        # Could stop here in real implementation
    Endif
Endfor

# Display result
Print ""
If found == true Then
    Print "✅ Found", target, "at position", position
Else
    Print "❌", target, "not found"
Endif

Endalgorithm

Example Output (searching for 67)

Enter number to search: 67 ✅ Found 67 at position 3

Binary Search

Binary Search is much faster but requires sorted data. It repeatedly divides the search space in half by comparing the middle element with the target.

How it Works:

Find the middle element
If middle equals target, found it!
If target is less than middle, search left half
If target is greater than middle, search right half
Repeat until found or no elements left

Example: Binary Search

Algorithm BinarySearch

# Array MUST be sorted for binary search!
var sortedArray = [11, 22, 33, 44, 55, 66, 77, 88, 99]
var target = Input "Enter number to find:"

var left = 0
var right = Size(sortedArray) - 1
var found = false
var position = -1

While left <= right and found == false Do
    # Calculate middle index
    var mid = (left + right) / 2
    
    If sortedArray[mid] == target Then
        found = true
        position = mid
    Else If sortedArray[mid] < target Then
        # Target is in right half
        left = mid + 1
    Else
        # Target is in left half
        right = mid - 1
    Endif
Endwhile

Print ""
If found == true Then
    Print "✅ Found", target, "at position", position
Else
    Print "❌", target, "not found"
Endif

Endalgorithm

Binary Search Example (searching for 55):

Array: [11, 22, 33, 44, 55, 66, 77, 88, 99]
Step 1: Check middle (index 4) = 55 ✅ FOUND!

Array: [11, 22, 33, 44, 55, 66, 77, 88, 99]
Searching for 22:
Step 1: Check middle (index 4) = 55 → target < 55, search LEFT
Step 2: Check middle of [11, 22, 33, 44] = 22 ✅ FOUND!

⚖️ Linear vs. Binary Search

Aspect	Linear Search	Binary Search
Data Requirement	Any array	Must be sorted
Speed	Slow on large data	Very fast
Complexity	Simple to implement	More complex
Best For	Small or unsorted arrays	Large sorted arrays

Real-World Applications

Phone Book Search

Example: Contact Search

Algorithm ContactSearch

var names = ["Alice", "Bob", "Charlie", "Diana", "Eve"]
var phones = ["555-0101", "555-0102", "555-0103", "555-0104", "555-0105"]

var searchName = Input "Enter name to search:"

var found = false

For i = 0 To Size(names) - 1
    If names[i] == searchName Then
        found = true
        Print ""
        Print "✅ Contact Found:"
        Print "Name:", names[i]
        Print "Phone:", phones[i]
    Endif
Endfor

If found == false Then
    Print ""
    Print "❌ Contact not found"
Endif

Endalgorithm

Product Search

Example: Inventory Search

Algorithm InventorySearch

var productIDs = [101, 205, 310, 415, 520, 625]
var productNames = ["Laptop", "Mouse", "Keyboard", "Monitor", "Webcam", "Headset"]
var prices = [999, 29, 79, 299, 89, 149]

var searchID = Input "Enter product ID:"

# Binary search (IDs are sorted)
var left = 0
var right = 5
var found = false
var index = -1

While left <= right and found == false Do
    var mid = (left + right) / 2
    
    If productIDs[mid] == searchID Then
        found = true
        index = mid
    Else If productIDs[mid] < searchID Then
        left = mid + 1
    Else
        right = mid - 1
    Endif
Endwhile

Print ""
If found == true Then
    Print "=== PRODUCT FOUND ==="
    Print "ID:", productIDs[index]
    Print "Name:", productNames[index]
    Print "Price: $", prices[index]
Else
    Print "❌ Product ID not found"
Endif

Endalgorithm

🔢 Search Functions

Example: Reusable Search Functions

Algorithm SearchFunctions

# Linear search function
Function LinearSearch(arr, size, target)
    For i = 0 To size - 1
        If arr[i] == target Then
            Return i  # Return index if found
        Endif
    Endfor
    Return -1  # Return -1 if not found
Endfunction

# Binary search function
Function BinarySearch(arr, size, target)
    var left = 0
    var right = size - 1
    
    While left <= right Do
        var mid = (left + right) / 2
        
        If arr[mid] == target Then
            Return mid
        Else If arr[mid] < target Then
            left = mid + 1
        Else
            right = mid - 1
        Endif
    Endwhile
    
    Return -1
Endfunction

# Test the functions
var unsorted = [5, 2, 8, 1, 9]
var sorted = [1, 2, 5, 8, 9]

var result1 = LinearSearch(unsorted, 5, 8)
Print "Linear search for 8:", result1

var result2 = BinarySearch(sorted, 5, 8)
Print "Binary search for 8:", result2

Endalgorithm

🎮 Advanced Search Example

Example: Find All Occurrences

Algorithm FindAllOccurrences

var grades = [85, 90, 85, 78, 90, 92, 85]
var searchGrade = Input "Enter grade to find:"

var positions[10]  # Store found positions
var count = 0

# Find all occurrences
For i = 0 To Size(grades) - 1
    If grades[i] == searchGrade Then
        positions[count] = i
        count = count + 1
    Endif
Endfor

# Display results
Print ""
If count > 0 Then
    Print "✅ Found", count, "occurrence(s) of", searchGrade
    Print "Positions:"
    For i = 0 To count - 1
        Print "  Index", positions[i]
    Endfor
Else
    Print "❌ Grade not found"
Endif

Endalgorithm

Search Optimization Tips

When to Use Each Algorithm

Use Linear Search When:

Array is small (under 100 elements)
Array is unsorted
Searching once or rarely
Simplicity is more important than speed

Use Binary Search When:

Array is large (1000+ elements)
Array is already sorted
Searching frequently
Speed is critical

Key Takeaways

✅ Linear Search: Check every element sequentially
✅ Binary Search: Divide and conquer (requires sorted data)
✅ Binary search is much faster for large datasets
✅ Linear search works on any array
✅ Return index if found, -1 if not found (common convention)
✅ Can search for multiple occurrences
✅ Choose algorithm based on data size and whether it's sorted

💪 Practice Exercises

Try These Exercises

Exercise 1: Recursive Binary Search

Implement binary search using recursion instead of a loop.

Exercise 2: Search Count

Modify linear search to count how many times a value appears in an array.

Exercise 3: Range Search

Find all elements in an array that fall within a given range (min to max).

Exercise 4: Dictionary Search

Create a word dictionary with definitions. Implement binary search to look up words (sorted alphabetically).

Fantastic Work!

You now understand fundamental searching algorithms! In the next lesson, we'll explore data structures like stacks, queues, and linked lists.