Table of Contents

Vocabulary

Linear Search Binary Search

Linear Search

<aside> 💡 Linear Search is a search algorithm that involves iterating through a collection of items one by one.

</aside>

Implementation

#include <iostream>
#include <vector>

bool linearSearch (std::vector<int>& list_of_nums, int desired_num) {
    for (int num : list_of_nums) {
        if (num == desired_num) {
            std::cout << num << std::endl;
            return true;
        }
    }
    return false;
}

int main() {
    std::vector<int> list_of_nums = {1, 4, 3, 2};
    linearSearch(list_of_nums, 3);
    return 0;
}

<aside> 💡 In this implementation, we are given a vector of 4 integers. To perform linear search, we will iterate through each and every element in the array and check if a certain element is our desired number. We will return true once we’ve found our desired number and return false if otherwise.

</aside>

Time Complexity Explanation

<aside> 💡 As $n$, which is represented by the size of the vector, grows larger, the time it takes for the algorithm to go through each and every element in the vector will increase proportionally. Thus, linear search has a time complexity of $O(n)$.

</aside>

Why Linear Search?

<aside> 💡 In terms of its advantages…

1. Linear Search does not require a collection type to be sorted which can make it faster in some cases.
2. Faster than other search algorithms on small/medium datasets

</aside>

Binary Search

<aside> 💡 Binary Search is another search algorithm that involves sorting a collection of items before searching for a target value with half of the values being eliminated in each iteration.

</aside>

Implementation

<aside> ❗ Note: Binary search can only be performed on sorted collection types! Remember to sort your array/vector before performing this search.

</aside>

#include <vector>

bool binarySearch (std::vector<int>& list_of_nums, int l_index, int r_index, int desired_num) {
    int i = l_index;
    int j = r_index;

    while (i < j) {
        int m_index = (i+j)/2;
        if (desired_num > list_of_nums.at(m_index))
            i = m_index + 1;
        else
            j = m_index;

    }

    return desired_num == list_of_nums.at(i);

}

int main() {
    //Recall: Vector must be sorted before performing binary search!
    std::vector<int> list_of_nums = {1, 2, 3, 4, 5, 6, 7};
    binarySearch(list_of_nums, 0, int(list_of_nums.size()-1), 3);
    return 0;
}