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.