# Search Algorithms

Input: a sequence; output: index in array or pointer to the element in the sequence.

## Sequential search

Complexity: O(n)

```
def sequential_search(a:'sequence', x:'num')->int:
for i in range(len(a)):
if a[i] == x:
return i;
return -1
```

## Binary search

Complexity: O(log(n))

Use: Any sorted indexed collection. Element access must be O(1). Usually used if collection is static, because if it requires insertions/deletions, than element access whould probably not be O(1). In short, good for sorted arrays.

Descrition: Recursively split array into halves and go to he half where the element belongs to. At each iteration 50% of array is discarded from the search. Stop when found or split led to 1 element.

```
def binary_search(ar:'indexed sequence', x:'num')->int:
start = 0
end = len(ar)-1
i = end // 2
while end > start:
v = ar[i]
if v == x:
return i
elif x < v:
# select the left half
end = i
else:
# select the right half
start = i + 1
i = (end - start) // 2
return -1
```

## Binary search tree

Definition: BST – balanced binary tree with property: **left child < parent** and **parent ≤ right child**

Complexity: O(log(n))

Used when there’s a need to maintain sorted order, and there’s a need for fast insertions/deletions. E.g. linked list organized as BST will allow for O(log(n)) searches and O(log(n)) modifications.