It looks like you're using Internet Explorer 11 or older. This website works best with modern browsers such as the latest versions of Chrome, Firefox, Safari, and Edge. If you continue with this browser, you may see unexpected results.

Professor Chuang Spring 2020 OER

An algorithm that solves the search problem retrieving information stored in a data structure.

There are primarily two search algorithms of interest:

1. Linear Search (can be performed on both sorted and unsorted arrays). O(n)

2. Binary Search (requires array to be sorted). O(logn)

Linear search conducts searches in sequential order

**O(n)**

```
For i from 0 to n–1
If i'th element is 50
Return true
Return false
```

This algorithm is called a **binary search** because you reduce the search by two (half the size) at every operation.

**O(logn)**

```
If no items
Return false
If middle item is 50
Return true
Else if 50 < middle item
Search left half
Else if 50 > middle item
Search right half
```