Search and find operations in Intro to Computing - Practice Problems & Coding Challenges

Challenge - 5 Problems

🧠 Conceptual

intermediate

Understanding Linear Search

Imagine you have a list of names on a paper. You want to find if the name "Alice" is in the list by checking each name one by one from the start.

Which description best matches this search method?

A Check each item from start to end until you find "Alice" or reach the end.

B Jump to the middle of the list and decide which half to search next.

C Sort the list first, then look for "Alice" using a fast method.

D Randomly pick names until you find "Alice".

💡 Hint

Think about checking names one by one in order.

Linear search means checking each item in order until the target is found or the list ends.

❓ trace

intermediate

Trace Binary Search Steps

You have a sorted list: [2, 4, 6, 8, 10, 12, 14]. You want to find the number 10 using binary search.

Which sequence of middle elements will the search check?

A 8, 10

B 8, 12, 10

C 10

D 6, 10

💡 Hint

Binary search picks the middle element each time and narrows down the search.

First middle is 8, since 10 > 8, search right half. Next middle is 12, since 10 < 12, search left half. Next middle is 10, found target.

❓ identification

advanced

Identify the Error in Search Algorithm

Consider this pseudocode for searching a value in a list:

start = 0
end = length(list) - 1
while start <= end:
  mid = (start + end) // 2
  if list[mid] == target:
    return mid
  elif list[mid] < target:
    start = mid + 1
  else:
    end = mid - 1
return -1

What is the mistake in this binary search implementation?

A The update of 'end' and 'start' is reversed; 'start' should increase when list[mid] < target.

B The function should return mid + 1 when the target is found.

C The condition in the while loop should be start < end, not start <= end.

D The calculation of 'mid' should use floating division instead of integer division.

💡 Hint

Think about which half to search next when the middle value is less than the target.

If list[mid] is less than target, the search should continue in the right half, so 'start' must be updated to mid + 1, not 'end'.

❓ Comparison

advanced

Compare Search Methods Efficiency

Which statement correctly compares linear search and binary search on a sorted list of 1,000,000 items?

A Linear search is faster because it checks items one by one, which is simpler.

B Linear search is faster because binary search requires sorting first.

C Both searches take the same time because they look for the same item.

D Binary search is faster because it divides the list and eliminates half each time.

💡 Hint

Think about how many items each method checks in the worst case.

Binary search reduces the search space by half each step, making it much faster on large sorted lists.

🚀 Application

expert

Find the Number of Comparisons in Binary Search

You use binary search to find a number in a sorted list of 1023 elements.

What is the maximum number of comparisons binary search will make before concluding?

A 11

B 9

C 10

D 8

💡 Hint

Binary search maximum comparisons relate to the power of 2 just greater than the list size.

Binary search maximum comparisons = ceiling of log2(n). For 1023, log2(1023) ≈ 9.99, so max comparisons = 10.

Practice

1. What is the main idea behind a linear search in a list?

easy

A. Check each item one by one until the target is found

B. Jump directly to the middle item and check only there

C. Sort the list first before searching

D. Use a map to find the item instantly

Solution

1. Step 1: Understand linear search method

   Linear search means looking at each item in order, one after another.

2. Step 2: Identify the correct description

   Only Check each item one by one until the target is found describes checking items one by one until the target is found.

3. Final Answer:

   Check each item one by one until the target is found -> Option A

4. Quick Check:

   Linear search = check items one by one [OK]

Hint: Linear search checks items in order until found [OK]

Common Mistakes:

• Thinking linear search jumps to middle item
• Confusing linear search with binary search
• Assuming list must be sorted first

2. Which of the following is the correct syntax to find the index of element 5 in a Python list named numbers?

easy

A. numbers.index(5)

B. index(numbers, 5)

C. numbers.find(5)

D. find(numbers, 5)

Solution

1. Step 1: Recall Python list method for finding index

   Python lists use the index() method to find the position of an element.

2. Step 2: Match method to syntax

   Only numbers.index(5) is correct syntax to find element 5's index.

3. Final Answer:

   numbers.index(5) -> Option A

4. Quick Check:

   List method to find index = index() [OK]

Hint: Use list.index(value) to find element position [OK]

Common Mistakes:

• Using find() which is for strings, not lists
• Trying to call index as a standalone function
• Confusing method name with other languages

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

items = [3, 7, 1, 9, 7]
print(items.index(7))

medium

A. Error

B. 3

C. 4

D. 1

Solution

1. Step 1: Understand list and index method

   The list items contains [3, 7, 1, 9, 7]. The index() method returns the first position of the value.

2. Step 2: Find first occurrence of 7

   7 appears first at position 1 (0-based index).

3. Final Answer:

   1 -> Option D

4. Quick Check:

   First 7 at index 1 [OK]

Hint: index() returns first match position [OK]

Common Mistakes:

• Choosing last occurrence index instead of first
• Confusing value with index
• Expecting error due to duplicate values

4. The following code is intended to find the index of 10 in the list data. What is wrong?

data = [4, 8, 10, 15]
position = data.find(10)
print(position)

medium

A. The list is missing the element 10

B. The list method should be index(), not find()

C. The print statement syntax is incorrect

D. The variable name 'position' is invalid

Solution

1. Step 1: Check method used on list

   Python lists do not have a find() method; they use index() to find element positions.

2. Step 2: Identify correct method

   Replacing find() with index() fixes the error.

3. Final Answer:

   The list method should be index(), not find() -> Option B

4. Quick Check:

   List search method = index() [OK]

Hint: Use index() for lists, find() is for strings [OK]

Common Mistakes:

• Assuming find() works on lists
• Thinking element 10 is missing
• Believing print syntax is wrong

5. You have a list of student names: students = ['Anna', 'Bob', 'Cara', 'Dan', 'Eli']. You want to check if 'Zoe' is in the list and print her position if found, otherwise print -1. Which code snippet correctly does this efficiently?

hard

A. print(students.find('Zoe'))

B. for i in range(len(students)):
if students[i] == 'Zoe':
print(i)
break

C. print(students.index('Zoe') if 'Zoe' in students else -1)

D. if 'Zoe' in students:
print(students.index('Zoe'))

Solution

1. Step 1: Understand the goal

   We want to check if 'Zoe' is in the list ('Zoe' not present) and print her position if found, else -1, efficiently without errors.

2. Step 2: Analyze options for correctness and efficiency

   print(students.index('Zoe') if 'Zoe' in students else -1) uses conditional expression to print index or -1 safely and efficiently. for i in range(len(students)): if students[i] == 'Zoe': print(i) break loops but prints nothing if not found. print(students.find('Zoe')) uses invalid find() for lists. if 'Zoe' in students: print(students.index('Zoe')) prints only if found, nothing otherwise.

3. Final Answer:

   print(students.index('Zoe') if 'Zoe' in students else -1) -> Option C

4. Quick Check:

   Safe check and index with conditional expression [OK]

Hint: Use conditional index with membership check to avoid errors [OK]

Common Mistakes:

• Using find() on list causing error
• Not printing -1 when element missing
• Writing longer loops instead of simple condition