Show understanding of linear and binary searching methods

19.1 Algorithms: Searching Methods 🔍

Linear Search (Brute‑Force) 🏁

Linear search is the simplest way to find an item in a list. Think of it like looking for a specific book in a stack of books that are not arranged in any order. You start at the first book and check each one until you find the target or run out of books.

Algorithm (pseudocode):

1. Set index = 0.
2. While index < length(array):
• If array[index] == target, return index.
• Increment index.
3. If the loop ends, return -1 (not found).

Example: Find 7 in [3, 8, 2, 7, 5].

• Check 3 → no.
• Check 8 → no.
• Check 2 → no.
• Check 7 → yes! Return index 3.

Time Complexity: In the worst case you look at every element: $$O(n)$$. In the best case you find it immediately: $$O(1)$$.

Binary Search (Divide & Conquer) ⚖️

Binary search is much faster but it only works on a list that is already sorted. Imagine you have a phone book sorted alphabetically and you want to find a name. Instead of checking every name, you look at the middle name, decide if the target is before or after, and then repeat on the relevant half. This halves the search space each time.

Algorithm (pseudocode):

1. Set low = 0, high = length(array) - 1.
2. While low <= high:
• Set mid = floor((low + high)/2).
• If array[mid] == target, return mid.
• Else if array[mid] < target, set low = mid + 1.
• Else set high = mid - 1.
3. If loop ends, return -1 (not found).

Example: Find 15 in sorted array [3, 7, 12, 15, 22, 29].

Time Complexity: Each step halves the search space, so the worst‑case time is $$O(\log n)$$. This is far better than linear search for large lists, but remember it only works on sorted data.

Choosing the Right Search

• Use linear search when the list is small or unsorted.
• Use binary search when the list is large and sorted.
• Always consider the cost of sorting if you need binary search on an unsorted list.

Remember: the best algorithm is the one that fits the problem constraints. Think of searching like a detective: sometimes you need to look at every clue (linear), other times you can skip half the clues each time (binary). Happy hunting! 🕵️‍♂️