Lesson 2. Search Algorithm

Lesson Objective

Understand the binary and linear search algorithms.
Identify the time complexity of the linear search and binary search algorithms.

Lesson Notes

Why use Search Algorithms?

Imagine you have a giant phonebook with millions of names. Finding a specific number would take forever if you flipped through each page!

That's where search algorithms come in. They're like clever tools that help you find things quickly in big piles of data. Instead of checking everything one by one, they use shortcuts and smart tricks to zoom in on exactly what you need.

Think of it like searching for your friend in a crowded playground. You wouldn't look at every single person, right? You'd probably scan for their hair color, clothes, or maybe even hear their voice. Search algorithms do something similar, but for data like phone numbers or addresses. They make finding things fast and easy, even in massive amounts of information!

Binary Search

This search algorithm keeps dividing a sorted list in half until the desired result is found.

Here is a list of names:

Ali	Brad	Cora	Fred	Iman	Lyra	Nila	Omar	Pham	Ruth	Vlad

We are searching for the name Nila. The list has 11 items. Examine the middle one first.

Ali	Brad	Cora	Fred	Iman	Lyra	Nila	Omar	Pham	Ruth	Vlad

The middle item in the list is Lyra. Lyra comes before Nila alphabetically so we can discard all the names to the left of Lyra, including Lyra. Now we only have 5 names to search.

Ali	Brad	Cora	Fred	Iman	Lyra	Nila	Omar	Pham	Ruth	Vlad

Examine the middle name of the remaining list. The middle name is Pham. Nila comes before Pham so we can discard all the names from Pham to Vlad.

Ali	Brad	Cora	Fred	Iman	Lyra	Nila	Omar	Pham	Ruth	Vlad

Two names remain. The "middle" name is taken to be the first one (e.g. In a list of 4 names, the 2nd name would be the middle one). In the list of 2, examine thie 1sr item (Nila). Nila has now been found.

Binary Search Algorithm

Here is a binary search algorithm. It has a time complexity of O(Log n).

function binarySearch(array, target)
    left = 0
    right = array.length - 1

    while left <= right
        mid = left + (right - left) / 2

        if array[mid] == target
            return mid
        else if array[mid] < target
            left = mid + 1
        else
            right = mid - 1

    return -1  // Target not found

Linear Search

Imagine you have a messy pile of clothes and you need to find a specific shirt. You wouldn't be able to quickly narrow it down by diving straight to the middle, right? That's like binary search, which needs things to be neatly ordered.

Instead, you'd likely pick up each item one by one, checking if it's the shirt you're looking for. That's similar to a linear search, which goes through things sequentially until it finds what you need.

So, when things are mixed up, a linear search is like sifting through, while a binary search is like aiming straight for the target when things are lined up perfectly.

146	23	54	12	89	223	9843	2	389

If the list to be searched is not sorted, it is not possible to do a binary search. A linear search may be carried out instead. Items are examined in the sequence. In the list above, to find the number 12, we would have to examine 146, 23, 54 and then 12.

Linear Search Algorithm

Here is a linear search algorithm. It has a time complexity of O(n).

function linearSearch(array, target)
    for each element in array
        if element is equal to target
            return index of element
    
    return -1 // Target not found

Search Comparisons

Linear search does not need a sorted list. Binary search more efficient than linear - faster on larger lists. Binary search can not be done on unsorted lists. Linear search not good for large lists

mrahmedcomputing