Implementation of two popular search algorithms:
In computer science, linear search or sequential search is a method for finding a target value within a list. It sequentially checks each element of the list for the target value until a match is found or until all the elements have been searched.
- Worst-case performance = O(n)
- Best-case performance = O(1)
- Average performance = O(n)
Binary search is an efficient algorithm for finding an item from an ordered list of items. It works by repeatedly dividing in half the portion of the list that could contain the item, until you've narrowed down the possible locations to just one.
- Worst-case performance = O(log n)
- Best-case performance = O(1)
- Average performance = O(log n)