Searching Algorithms

• The 2 searching algorithms used are:

  • Linear Search
  • Binary Search
• Linear search is a search algorithm that starts at the beginning of the list and checks each item in the list until it finds the item it is looking for.
• Binary search is a search algorithm that locates the middle element of a sorted array first, and determines if the element being search is in the first or second half of the array. This process of locating the middle element of subarrays continues until the element is found.
• Time Complexity of Linear Search:

  Best Case: O( 1 )

  Average Case: O( N/2 )

  Worst Case: O( N )
• Time Complexity of Binary Search:

  Best Case: O( 1 )

  Average Case: O( log N )

  Worst Case: O( log_2 N )
• Advantages of Linear Search:

  • Additional data can simply be appended to the list without sorting
  • Straightforward and intuitive
  • Works well with small datasets
• Disadvantages of Linear Search:

  • Inefficient with large datasets
  • Missing data cannot be confirmed until every element in the array has been compared
• Advantages of Binary Search:

  • Efficient with large datasets
  • Missing data can be identified quickly
• Disadvantages of Binary Search:

  • Array must be sorted
  • Adding or deleting an element is slow, and might require a second round of re-sorting