Searching algorithms (linear, binary) in Intro to Computing - Interactive Code Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to perform a linear search for the target in the list.

Intro to Computing

def linear_search(lst, target):
    for i in range(len(lst)):
        if lst[i] == [1]:
            return i
    return -1

Drag options to blanks, or click blank then click option'

Alst

Btarget

Ci

Dlen

Attempts:

3 left

💡 Hint

Common Mistakes

Using the index variable instead of the target value in the comparison.

Comparing the list to the target instead of the element at the current index.

The code compares each element in the list to the target value to find its position.

2fill in blank

medium

Complete the code to perform a binary search on a sorted list.

Intro to Computing

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

Drag options to blanks, or click blank then click option'

Atarget

Bmid

Clow

Dhigh

Attempts:

3 left

💡 Hint

Common Mistakes

Comparing the middle index instead of the middle element to the target.

Using the wrong variable in the equality check.

The binary search compares the middle element lst[mid] with the target to decide where to search next.

3fill in blank

hard

Fix the error in the binary search condition to correctly update the search range.

Intro to Computing

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

Drag options to blanks, or click blank then click option'

Alow - 1

Bmid + 1

Cmid - 1

Dhigh + 1

Attempts:

3 left

💡 Hint

Common Mistakes

Setting high to mid + 1 which expands the search range incorrectly.

Using low or high incorrectly in the update.

When the middle element is greater than the target, the search range's high index should move to mid - 1 to search the left half.

4fill in blank

hard

Fill both blanks to create a dictionary comprehension that maps words to their lengths only if length is greater than 3.

Intro to Computing

lengths = {word: [1] for word in words if [2]

Drag options to blanks, or click blank then click option'

Alen(word)

Blen(word) > 3

Cword.startswith('a')

Dword

Attempts:

3 left

💡 Hint

Common Mistakes

Using the word itself as the value instead of its length.

Using a condition unrelated to length.

The dictionary comprehension maps each word to its length using len(word), but only includes words where the length is greater than 3.

5fill in blank

hard

Fill all three blanks to create a dictionary comprehension that maps uppercase words to their lengths only if length is less than 5.

Intro to Computing

result = [1]: [2] for word in words if [3]

Drag options to blanks, or click blank then click option'

Aword.upper()

Blen(word)

Clen(word) < 5

Dword.lower()

Attempts:

3 left

💡 Hint

Common Mistakes

Using the original word as the key instead of uppercase.

Using incorrect length conditions.

Mixing up keys and values.

The comprehension maps each word converted to uppercase (word.upper()) to its length (len(word)), but only includes words shorter than 5 characters.

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