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.

Practice

1. Which of the following is true about linear search?

easy

A. It checks each item one by one until it finds the target.

B. It requires the list to be sorted before searching.

C. It splits the list into halves to find the target quickly.

D. It only works on numbers, not text.

Solution

1. Step 1: Understand linear search method

   Linear search goes through each item in the list one by one to find the target.

2. Step 2: Compare with other search methods

   Binary search splits the list and requires sorting, but linear search does not.

3. Final Answer:

   It checks each item one by one until it finds the target. -> Option A

4. Quick Check:

   Linear search = check items one by one [OK]

Hint: Linear search checks items one by one [OK]

Common Mistakes:

• Thinking linear search needs sorted list
• Confusing linear search with binary search
• Believing linear search only works on numbers

2. Which of the following is the correct syntax for a linear search loop in Python to find target in arr?

easy

A. for i in arr:
if i == target
return True

B. for i in range(len(arr)):
if arr[i] = target:
return True

C. while i < len(arr):
if arr[i] == target
return True

D. for i in arr:
if i == target:
return True

Solution

1. Step 1: Check correct loop syntax

   for i in arr: if i == target: return True uses a for loop to iterate over each element in arr correctly.

2. Step 2: Verify condition and syntax

   for i in arr: if i == target: return True uses '==' for comparison and proper indentation, which is correct.

3. Final Answer:

   for i in arr: if i == target: return True -> Option D

4. Quick Check:

   Correct for loop and comparison syntax [OK]

Hint: Use '==' for comparison and proper indentation [OK]

Common Mistakes:

• Using single '=' instead of '==' for comparison
• Missing colon ':' after if statement
• Incorrect indentation causing syntax errors

3. What will be the output of the following Python code?

def binary_search(arr, target):
    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

arr = [2, 4, 6, 8, 10]
print(binary_search(arr, 6))

medium

A. -1

B. 1

C. 2

D. 3

Solution

1. Step 1: Understand binary search on sorted list

   The list is sorted: [2, 4, 6, 8, 10]. Target is 6.

2. Step 2: Trace the binary search steps

   Initial low=0, high=4, mid=2. arr[2]=6 matches target, so return 2.

3. Final Answer:

   2 -> Option C

4. Quick Check:

   Index of 6 in list = 2 [OK]

Hint: Binary search returns index of target if found [OK]

Common Mistakes:

• Not using zero-based index
• Confusing mid calculation
• Assuming binary search works on unsorted lists

4. The following code is intended to perform a binary search but has an error. What is the error?

def binary_search(arr, target):
    low, high = 0, len(arr)
    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

medium

A. The mid calculation should use float division.

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

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

D. The function should return True instead of index.

Solution

1. Step 1: Check initialization of high index

   High is set to len(arr), which is out of valid index range (0 to len(arr)-1).

2. Step 2: Understand index range in Python lists

   List indices go from 0 to len(arr)-1, so high must be len(arr)-1 to avoid index error.

3. Final Answer:

   The high index should be len(arr) - 1, not len(arr). -> Option B

4. Quick Check:

   High index = len(arr) - 1 [OK]

Hint: High index must be last valid index (len-1) [OK]

Common Mistakes:

• Setting high to len(arr) causes index out of range
• Using float division for mid index
• Wrong loop condition causing infinite loop

5. You have a sorted list of 1024 numbers. You want to find if the number 500 is in the list. Which search method is faster and why?

hard

A. Binary search, because it splits the list and reduces search steps quickly.

B. Binary search, but only if the list is unsorted.

C. Linear search, because it works only on sorted lists.

D. Linear search, because it checks each item one by one.

Solution

1. Step 1: Identify list size and sorting

   The list has 1024 numbers and is sorted, which suits binary search.

2. Step 2: Compare search methods speed

   Binary search halves the search space each step, so it finds the target in about 10 steps (log2(1024) = 10), much faster than linear search.

3. Final Answer:

   Binary search, because it splits the list and reduces search steps quickly. -> Option A

4. Quick Check:

   Binary search faster on sorted large lists [OK]

Hint: Use binary search on sorted big lists for speed [OK]

Common Mistakes:

• Choosing linear search for large sorted lists
• Thinking binary search works on unsorted lists
• Ignoring the list size impact on search speed