Linear Search
In computer science, linear search or sequential search is a method for finding a particular value in a list, that consists of checking every one of its elements, one at a time and in sequence, until the desired one is found.
- Time Complexity -
O(n)
Binary Search
This search requires a sorted list of items, but it's considerably faster than linear search.
- Time Complexity -
O(lg n)
- Pseudocode -
BINARY-SEARCH(A, a, b, x)
1 if a > b
2 then return 0
3 mid ← ⌊(a + b)/2⌋
4 if x = A[mid]
5 then return mid
6 else if x < A[mid]
7 then BINARY-SEARCH(A, a, mid-1, x)
8 else BINARY-SEARCH(A, mid+1, b, x)
Hash Search
One can lookup an item in constant time. If the list is constructed as a hash table, or hash map, data structure. (Note that if the key range is small and in integer format, one can use an array in place of a hash table.)
- Time Complexity -
O(1)
Substring Search | 