Foundations‎ > ‎Algorithms‎ > ‎

Search

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