Binary Search vs Linear Search Real Cost Difference in DSA Python - Interactive Comparison Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to perform a linear search that returns the index of the target or -1 if not found.

DSA Python

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

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

Atarget

Bi

Carr

Dlen(arr)

Attempts:

3 left

💡 Hint

Common Mistakes

Using the index variable instead of the target value

Comparing with the whole array instead of the target

The function compares each element with the target. So, the blank should be target.

2fill in blank

medium

Complete the code to perform a binary search on a sorted list and return the index of the target or -1 if not found.

DSA Python

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] < [1]:
            low = mid + 1
        else:
            high = mid - 1
    return -1

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

Alow

Bmid

Ctarget

Dhigh

Attempts:

3 left

💡 Hint

Common Mistakes

Comparing with the index instead of the target

Using wrong variable in comparison

We compare the middle element arr[mid] with the target to decide which half to search next.

3fill in blank

hard

Fix the error in the binary search code by completing the blank to correctly update the high pointer.

DSA Python

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 = [1]
    return -1

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

Amid - 1

Blow - 1

Cmid + 1

Dhigh + 1

Attempts:

3 left

💡 Hint

Common Mistakes

Setting high to mid + 1 which skips needed elements

Using low - 1 which is unrelated

When the middle element is greater than the target, we move the high pointer to mid - 1 to search the left half.

4fill in blank

hard

Fill both blanks to create a dictionary comprehension that maps each word to its length only if the length is greater than 3.

DSA Python

words = ['apple', 'bat', 'carrot', 'dog']
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 > 3

Dword.length > 3

Attempts:

3 left

💡 Hint

Common Mistakes

Using the word itself in the condition instead of its length

Using incorrect syntax for length

The dictionary maps each word to its length using len(word). The condition filters words with length greater than 3 using len(word) > 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 or equal to 5.

DSA Python

words = ['apple', 'bat', 'carrot', 'dog']
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 lowercase instead of uppercase

Incorrect condition syntax

The dictionary keys are uppercase words using word.upper(). The values are lengths using len(word). The condition filters words with length less than or equal to 5 using len(word) <= 5.

Practice

1. Which search algorithm is generally faster on a sorted list of 1,000,000 elements?

easy

A. Binary Search

B. Linear Search

C. Both are equally fast

D. Neither works on sorted lists

Solution

1. Step 1: Understand the search algorithms

   Binary Search divides the list in half repeatedly, while Linear Search checks each element one by one.

2. Step 2: Compare efficiency on large sorted lists

   Binary Search takes about log2(1,000,000) ≈ 20 steps, Linear Search takes up to 1,000,000 steps.

3. Final Answer:

   Binary Search -> Option A

4. Quick Check:

   Binary Search is faster on sorted lists [OK]

Hint: Binary Search halves search space; Linear checks all [OK]

Common Mistakes:

• Thinking Linear Search is faster on sorted lists
• Confusing sorted and unsorted list requirements
• Ignoring the difference in number of steps

2. Which of the following is the correct syntax to start a binary search on a sorted list named arr in Python?

easy

A. arr.binary_search(target)

B. bisect.bisect_left(arr, target)

C. binary_search(arr, target)

D. search(arr, target)

Solution

1. Step 1: Recall Python's binary search method

   Python's standard library uses the bisect module for binary search operations.

2. Step 2: Identify correct function call

   bisect.bisect_left(arr, target) returns the insertion point using binary search.

3. Final Answer:

   bisect.bisect_left(arr, target) -> Option B

4. Quick Check:

   Use bisect module for binary search in Python [OK]

Hint: Use bisect module for binary search in Python [OK]

Common Mistakes:

• Assuming binary_search is a built-in function
• Trying to call binary_search as a method on list
• Using generic search functions without binary search

3. What is the output of the following code snippet?

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

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

medium

A. 3

B. 4

C. -1

D. Error

Solution

1. Step 1: Trace the linear search function

   The function checks each element from index 0 to 4 for the target 8.

2. Step 2: Find the target index

   At index 3, arr[3] is 8, so function returns 3.

3. Final Answer:

   3 -> Option A

4. Quick Check:

   Index of 8 in list is 3 [OK]

Hint: Linear search returns index of first match [OK]

Common Mistakes:

• Confusing index with value
• Assuming zero-based index starts at 1
• Expecting output to be value instead of index

4. Find the error in this binary search implementation and select the correct fix:

def binary_search(arr, target):
    low = 0
    high = 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. No error, code is correct

B. Change while low <= high to while low < high

C. Change mid calculation to mid = (low + high + 1) // 2

D. Change high = len(arr) to high = len(arr) - 1

Solution

1. Step 1: Check high initialization

   Indexing in Python is zero-based, so last index is len(arr) - 1, not len(arr).

2. Step 2: Understand loop condition and indexing

   Using high = len(arr) causes index out of range error when mid equals len(arr).

3. Final Answer:

   Change high = len(arr) to high = len(arr) - 1 -> Option D

4. Quick Check:

   High must be last valid index [OK]

Hint: High index = length minus one for zero-based lists [OK]

Common Mistakes:

• Setting high to length instead of last index
• Changing loop condition incorrectly
• Modifying mid calculation unnecessarily

5. You have a sorted list of 10,000 elements and want to find a target value. Which search method is more efficient in terms of average number of comparisons, and why?

Options:
A) Linear Search because it checks elements sequentially.
B) Linear Search because it works on sorted lists.
C) Binary Search because it reduces search space by half each step.
D) Binary Search because it checks every element once.

hard

A. Linear Search because it checks elements sequentially.

B. Linear Search because it works on sorted lists.

C. Binary Search because it reduces search space by half each step.

D. Binary Search because it checks every element once.

Solution

1. Step 1: Analyze average comparisons for Linear Search

   Linear Search checks elements one by one, so average comparisons ≈ 10,000/2 = 5,000.

2. Step 2: Analyze average comparisons for Binary Search

   Binary Search halves the list each step, so comparisons ≈ log2(10,000) ≈ 14.

3. Step 3: Compare efficiency

   Binary Search requires far fewer comparisons on large sorted lists.

4. Final Answer:

   Binary Search because it reduces search space by half each step. -> Option C

5. Quick Check:

   Binary Search is more efficient on sorted lists [OK]

Hint: Binary Search halves search space, fewer comparisons [OK]

Common Mistakes:

• Thinking Linear Search is faster on sorted lists
• Believing Binary Search checks every element
• Ignoring the effect of list size on comparisons