Searching algorithms (linear, binary) in Intro to Computing - Practice Problems & Coding Challenges

Challenge - 5 Problems

🧠 Conceptual

intermediate

Understanding Linear Search Steps

Imagine you have a list of 7 books on a shelf, and you want to find a specific book by its title. You start checking each book from the left until you find the one you want.

Which of the following best describes the number of checks you might do in the worst case?

A You check half the books, so about 3 or 4 checks.

B You check only the middle book, so 1 check.

C You check every book until the last one, so up to 7 checks.

D You check books randomly until you find it.

💡 Hint

Think about how linear search works by checking each item one by one.

Linear search checks each item in order until it finds the target or reaches the end. In the worst case, it checks all items.

❓ trace

intermediate

Trace Binary Search on a Sorted List

Given the sorted list [2, 4, 6, 8, 10, 12, 14], you want to find the number 10 using binary search.

How many comparisons does binary search make before finding 10?

A 3 comparisons

B 1 comparison

C 2 comparisons

D 4 comparisons

💡 Hint

Binary search splits the list in half each time and compares the middle element.

Binary search compares middle elements: first 8 (not 10), then right half middle 12 (not 10), then left half middle 10 (found). Total 3 comparisons.

❓ Comparison

advanced

Comparing Efficiency of Linear vs Binary Search

You have two lists of 1,000 numbers each. One list is unsorted, the other is sorted. You want to find if the number 500 exists.

Which statement correctly compares the number of checks each search method might do?

A Binary search works only on unsorted lists, so it checks all items.

B Linear search on unsorted list may check up to 1,000 items; binary search on sorted list checks about 10 items.

C Both searches check about 500 items on average.

D Linear search on unsorted list checks about 10 items; binary search on sorted list checks 1,000 items.

💡 Hint

Recall how binary search halves the search space each time.

Linear search checks items one by one, possibly all 1,000. Binary search halves the list each time, so about log2(1000) ≈ 10 checks.

❓ identification

advanced

Identify the Error in Binary Search Implementation

Look at this Python code snippet for binary search on a sorted list:

def binary_search(arr, target):
    low = 0
    high = len(arr) - 1
    while low <= high:
        mid = (low + high) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1

What is the main error that will cause a runtime problem?

A The high index should be len(arr) - 1, not len(arr).

B The mid calculation should use (low - high) // 2.

C The loop condition should be while low < high, not <=.

D The function should return None instead of -1 when not found.

💡 Hint

Think about valid index ranges in Python lists.

List indices go from 0 to len(arr)-1. Setting high to len(arr) causes an index out of range error.

🚀 Application

expert

Determine Output of Mixed Search Algorithm

Consider this Python code that searches for a number in a list:

def mixed_search(arr, target):
    if arr != sorted(arr):
        # Use linear search
        for i, val in enumerate(arr):
            if val == target:
                return i
        return -1
    else:
        # Use binary search
        low, high = 0, len(arr) - 1
        while low <= high:
            mid = (low + high) // 2
            if arr[mid] == target:
                return mid
            elif arr[mid] < target:
                low = mid + 1
            else:
                high = mid - 1
        return -1

print(mixed_search([3, 1, 4, 2], 4))

What is the output when running this code?

A -1

B 0

C 3

D 2

💡 Hint

Check if the list is sorted and which search method runs.

The list [3,1,4,2] is not sorted, so linear search runs. The value 4 is at index 2, so output is 2.