In computer science, a search algorithm is any algorithm which solves the search problem, namely, to retrieve information stored within some data structure.
In this article we will take a look at two simple search algorithms.
Linear search
How it works ?
The easiest search algorithm you can imagine ! Also known as sequential search this is a method for finding an element within a list. It sequentially checks each element of the list until a match is found or the whole list has been searched.
Features
- It is used for unsorted and unordered small list of elements.
- It has a time complexity of O(n), which means the time is linearly dependent on the number of elements, which is not bad, but not that good too.
- It has a very simple implementation.
Example
Binary search
How it works ?
Also known as half-interval search, this search algorithm finds the position of a target value within a sorted array.Binary search compares the target value to the middle element of the array. If they are not equal, the half in which the target cannot lie is eliminated and the search continues on the remaining half, again taking the middle element to compare to the target value, and repeating this until the target value is found.
Features
- It is great to search through large sorted arrays.
- It has a time complexity of O(log n) which is a very good time complexity. (For 2048 records, it will take only 12 steps maximum to find the target !)
- It has a simple implementation.
Example
In the next article, we will see together what is Dynamic Programming !
