Searching represents how we solve the problem of finding information.
A simple problem has an input of some values, and an output of a bool, whether or not a particular value is in the array.
To define searching algorithms, they are designed to check for an element or retrieve it from any data structured it is stored in.
These algorithms are generally classified into two categories:
- sequential search: the array is traversed sequentially and every element is checked (linear search).
- interval search: designed for searching sorted data structures (binary search).
Linear Search is defined as a sequential search algorithm that starts at one end and goes through each elements of a list until the desired element is found, otherwise the search continues until the end of the set.
- Worst-case performance - O(n)
- Best-case performance - O(1)
- Average performance - O($n^2)
- Worst-case space complexity - O(1)
- Representing 'Linear Search' in pseudocode:
for each door from left to right
if number is behind door
return True
return FalseNOTE: the return False is outside the loop, since we only want to do that after we've looked behind all doors.
Binary Search find the position of a target value within a sorted list. It compares the target value to the middle element of the array, if they are not equal the half in which the target cannot be is eliminated and the search continues in the remaining half, continuing until the target value is found. If the search ends with the remaining half being empty, the target is not in the list.
- Worst-case performance - O(log n)
- Best-case performance - O(1)
- Average performance - O(log n)
- Worst-case space complexity - O(1)
- Representing 'Binary Search' in pseudocode:
if no doors
return False
if number behind middle door
return True
else if number < middle door
search left half
else if number > middle door
search right halfNOTE: remember to check whether there are no doors left, since that means our number isn't behind any of them.