Overview of Searching Algorithms

<aside> <img src="/icons/table_red.svg" alt="/icons/table_red.svg" width="40px" /> Table of Contents

</aside>

<aside> 💡

1. Linear Search </aside>

<aside> 💡

1. Binary Search </aside>

Linear Search

1. Searching Algorithms

   1. Searching algorithms are methods used to retrieve a specific element (key) from a collection of elements. Here, we will focus on two key searching techniques: Linear Search and Binary Search.

   ---

2. Linear Search

   1. Linear search is the simplest searching algorithm. It checks each element in the collection sequentially until the desired element (key) is found or the end of the collection is reached.
   2. Steps of Linear Search
      1. Start at the first element of the array.
      2. Compare the current element with the key.
      3. If the current element matches the key:
         1. Return the index of the element.
      4. If the current element does not match the key:
         1. Move to the next element.
      5. Repeat until the key is found or the array ends.
      6. If the array ends and the key is not found, return "key not found."

   ---

3. Algorithm for Linear Search

   1. Input: Array $A$ of size $n$, key $x$.

   2. Output: Index of $x$ if found; otherwise, -1.

   3. For $i = 0$ to $n-1$:

      1. If $A[i] == x$:
      2. Return $i$.

   4. Return -1.

   5. Python Code for Linear Search

      def linear_search(arr, key):
          for i in range(len(arr)):
              if arr[i] == key:  # Compare each element
                  return i       # Return the index if found
          return -1              # Return -1 if not found
      

   ---

4. Time Complexity of Linear Search

   1. The time complexity depends on the number of comparisons:
   2. Best Case: Key is found at the first position.
      1. Time Complexity: $T(n) = O(1)$.
   3. Worst Case: Key is not in the array, or it is the last element.
      1. Comparisons: $n$.
      2. Time Complexity: $T(n) = O(n)$.
   4. Average Case: Key is expected to be somewhere in the middle.
      1. Comparisons: $(n/2)$.
      2. Time Complexity: $T(n) = O(n)$.
   5. Equation Representation:

      1. Let $n$ be the number of elements.

      2. For $n$ elements, the total comparisons in the worst case are:

         $$ T(n) = n \quad \implies \quad O(n). $$

   ---