Welcome to Searching Algorithms!

Have you ever spent ages rummaging through your school bag trying to find a pen, or quickly looked up a word in a dictionary? If so, you have already used searching strategies in real life! In computer science, we call these step-by-step methods searching algorithms.

Don't worry if this sounds tricky at first. By the end of these study notes, you will understand exactly how computers look for information, the two main methods they use, and how to choose the best one for any job.

1. Key Terms and Core Ideas

Before we dive in, let's understand the essential building blocks:

• Algorithm: A step-by-step set of precise, unambiguous instructions designed to solve a problem or complete a task.
• Searching Algorithm: A structured computational method used to locate a specific item within a collection of data (such as a list) or confirm that the item is missing.
• Target (or Search Key): The specific value or item you are searching for.
• Element (or Item): An individual value inside the list.
• Index: The numerical position of an item in a list.
• Comparison: An operation where the computer checks the target against an item in the list to see if it is equal, smaller, or larger.
• Efficiency (Utility): A measure of how many comparisons an algorithm needs to make to find an item, especially as the list gets bigger.

Quick Takeaway: Whenever a computer searches for something, it works through a list and makes comparisons until it finds the target or reaches the end.

Imagine looking for a specific playing card in a shuffled deck. You start at the top, look at the first card, then the second, then the third, checking them one by one in order until you find the card you want.

This is exactly how a linear search works!

How Linear Search Works Step-by-Step

1. Start at the very first element (position 1 or index 0) of the list.
2. Compare the current element with your target.
3. If they match, the search stops immediately: report "Found!" along with its position.
4. If they do not match, move forward to the next item in the list.
5. Repeat steps 2 to 4 until either the item is found, or you reach the very end of the list without a match (report "Not found").

Trace Example

Let's search for the target value 7 in this unsorted list: [4, 9, 7, 2]
• Step 1: Check position 1 (Value: 4). Is \(4 = 7\)? No. Move to next.
• Step 2: Check position 2 (Value: 9). Is \(9 = 7\)? No. Move to next.
• Step 3: Check position 3 (Value: 7). Is \(7 = 7\)? Yes! Item found at position 3.

Performance of Linear Search

Let \(n\) be the total number of items in the list.
• Best-Case Scenario: \(1\) comparison (the item is right at the very start).
• Worst-Case Scenario: \(n\) comparisons (the item is at the very end, or not in the list at all).
• Average-Case Scenario: Approximately \(\frac{n}{2}\) comparisons.

Advantages and Disadvantages

• Advantage: Works on any list, whether it is sorted or completely unsorted.
• Advantage: Very simple to understand and program.
• Disadvantage: Very slow and inefficient for large lists (searching 1,000,000 items could take up to 1,000,000 comparisons!).

Quick Takeaway: Linear search checks items one by one from start to finish. It requires no sorting, but becomes very slow on large lists.

3. Binary Search (Divide and Conquer)

Imagine guessing a secret number between 1 and 100. If you guess 50 and are told "Higher", you instantly ignore all numbers from 1 to 50! You have just cut your search space in half with one guess.

This is the power of a binary search.

The Golden Rule of Binary Search

Crucial Requirement: The data MUST BE SORTED (in numerical or alphabetical order). Binary search will fail completely on an unsorted list!

How Binary Search Works Step-by-Step

1. Identify the search range with two pointers: start (the first position) and end (the last position).
2. Calculate the middle position using integer division:
\(\text{mid} = \lfloor(\text{start} + \text{end}) / 2\rfloor\)
3. Compare the middle element with the target:
• If the middle element equals the target: Found! Search ends.
• If the target is smaller than the middle element: Discard the middle item and the entire upper half by setting \(\text{end} = \text{mid} - 1\).
• If the target is greater than the middle element: Discard the middle item and the entire lower half by setting \(\text{start} = \text{mid} + 1\).
4. Repeat steps 2 and 3 on the remaining sub-list until the item is found, or until start becomes greater than end (which means the item is "Not found").

Trace Example

Let's search for the target value 19 in this sorted list of 7 items: [3, 6, 8, 12, 15, 19, 24]
• Pass 1: \(\text{start} = 1\), \(\text{end} = 7\). Middle position is \(\lfloor(1 + 7) / 2\rfloor = 4\). Element at position 4 is 12.
Is \(19 = 12\)? No. Since \(19 > 12\), ignore the left half! Set \(\text{start} = 4 + 1 = 5\).
• Pass 2: \(\text{start} = 5\), \(\text{end} = 7\). Middle position is \(\lfloor(5 + 7) / 2\rfloor = 6\). Element at position 6 is 19.
Is \(19 = 19\)? Yes! Item found at position 6 in just 2 comparisons.

Performance of Binary Search

• Best-Case Scenario: \(1\) comparison (the item is right in the exact middle of the list on the first try).
• Worst-Case / Average-Case: Approximately \(\log_2(n)\) comparisons. Every comparison cuts the remaining list in half!
• Did you know? In a sorted list of 1,000 items, while a linear search might take up to 1,000 steps, a binary search takes at most \(\lceil\log_2(1000)\rceil = 10\) comparisons!

Advantages and Disadvantages

• Advantage: Extremely fast and efficient on large amounts of data.
• Disadvantage: The list must be sorted first. Sorting takes extra effort if the list is unsorted.
• Disadvantage: More complex to trace and write than linear search.

Quick Takeaway: Binary search repeatedly checks the middle item and cuts the search space in half. It is lightning-fast, but only works on sorted lists.

When solving problems, computer scientists must choose the right tool for the job. Here is how the two algorithms compare:

Data Requirement:
• Linear Search: Any dataset (works on unsorted or sorted data).
• Binary Search: Must be sorted (ascending or descending order).

Search Mechanism:
• Linear Search: Checks one item at a time sequentially from start to end.
• Binary Search: Repeatedly checks the midpoint and cuts the search area in half.

Best-Case Comparisons:
• Linear Search: \(1\)
• Binary Search: \(1\)

Worst-Case Comparisons:
• Linear Search: \(n\) (the total number of items in the list).
• Binary Search: \(\log_2(n)\) (rounded up to the nearest whole number).

Best Used For:
• Linear Search: Short lists, unsorted data, or one-off quick searches.
• Binary Search: Very large datasets and lists that are already sorted and searched frequently.

5. Common Mistakes to Avoid

Watch out for these common traps when answering questions:

1. Using Binary Search on Unsorted Lists:
Mistake: Trying to do a binary search on a list like [9, 2, 8, 1].
Correction: Binary search relies entirely on order. If the list is not sorted, throwing away a half-list might accidentally throw away the target!

2. Forgetting What Worst-Case Means:
Mistake: Thinking linear search always takes \(n\) steps.
Correction: Linear search only takes \(n\) steps in the worst case (when the item is at the very end or not in the list). If you are lucky, it takes just \(1\) step.

3. Midpoint Calculation Errors:
Mistake: Getting confused when dividing an even sum.
Correction: Always use integer division (round down to the floor value), for example: \(\lfloor(1 + 4) / 2\rfloor = \lfloor 2.5 \rfloor = 2\).

4. Forgetting the "Not Found" Case:
Mistake: Assuming the target will always be in the list.
Correction: A good algorithm must handle missing items properly (reaching the end of the list in linear search, or when \(\text{start} > \text{end}\) in binary search).

6. Chapter Summary Checklist

Before you finish, check that you can:
• Define what a searching algorithm, target, and comparison are.
• Explain the step-by-step process of a linear search and trace it on a list.
• State the best-case (\(1\)) and worst-case (\(n\)) performance of linear search.
• Explain the step-by-step process of a binary search and calculate midpoints using integer division.
• Remember that binary search requires a sorted list.
• Explain why binary search is far more efficient than linear search for large datasets.