Searching algorithms (linear, binary) in Intro to Computing - Real World Applications

Real World Mode - Searching algorithms (linear, binary)

Finding a Book on a Bookshelf

Imagine you want to find a specific book on a bookshelf. There are two common ways you might look for it. First, you could start at one end and check each book one by one until you find the right one. This is like linear search. It's simple but can take a while if the book is near the end or not there at all.

Alternatively, if the books are arranged alphabetically by title, you can use a faster method called binary search. You open the shelf in the middle, check the book's title, and decide if your book would be to the left or right. Then you only look in that half, repeating the process until you find the book. This method is much quicker but only works if the books are sorted.

Mapping Searching Algorithms to Bookshelf Analogy

Computing Concept	Real-World Equivalent	Explanation
Linear Search	Checking each book one by one	Look at every book from start to finish until you find the target.
Binary Search	Opening the shelf in the middle and choosing half	Use the sorted order to split the search area in half repeatedly.
Sorted Data	Books arranged alphabetically	Binary search requires the books to be in order to decide which half to search.
Unsorted Data	Books randomly placed	Linear search works regardless of order but is slower.
Search Target	The specific book you want	The item you are trying to find on the shelf.

A Day in the Life: Finding a Cookbook

Imagine you just moved into a new home and unpacked your kitchen books. They are all mixed up on a shelf. You want to find your favorite cookbook. You start at the left and look at each book's title until you find it. This is like a linear search -- simple but might take time.

Later, you decide to organize your books alphabetically. Next time you want that cookbook, you open the shelf in the middle, see the title, and realize your book is in the left half. You open the middle of that half next, and so on, quickly narrowing down to your cookbook. This is binary search -- much faster because the books are sorted.

Where the Bookshelf Analogy Breaks Down

• Data Size: Real bookshelves have limited space, but computers can handle millions of items. The analogy doesn't show how search time grows with very large data.
• Random Access: In binary search, you can jump to the middle instantly. In a physical bookshelf, you might need to move books or physically reach, which takes time.
• Data Structure: Computers use arrays or lists with direct access, unlike physical bookshelves where accessing the middle might be slower.
• Updates: Adding or removing books affects order; in computers, maintaining sorted data can be automated and efficient.

Self-Check Question

In our bookshelf analogy, if the books are not arranged in any order, which search method would you use to find your book?

Answer: Linear search -- checking each book one by one.

Key Result

Searching algorithms are like finding a book on a bookshelf: linear search checks each book one by one, binary search splits the shelf in half if books are sorted.

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