Foundations‎ > ‎Algorithms‎ > ‎

## 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)`