# Sequential vs Binary Search¶

*Written by PChan on 2017-04-14*

## Sequential Search¶

Sequential search, sometimes called linear search, is the most basic searching algorithm. Start at either end of the list and traverse the list sequentially (one-by-one) until you have found your element or until there are no more elements to examine.

## Binary Search¶

If the list that you are examining is already sorted, we can use a faster algorithm: the binary search.

- Start searching in the middle of the array
- Stop if you have found your element.
- Otherwise...
- If the element you are looking for is greater than the middle element, examine the middle element of the right sublist
- If the element you are looking for is less than the middle element, examine the middle element of the left sublist

- Repeat step 3 until you have either found your element or the sublist that you are looking for contains no elements

## Summary¶

Here are some questions to ponder over (in order of ascending difficulty):

- When can you use the binary search? When would you need to use the sequential search?
- What is the best case scenario for sequential search? Worst case scenario?
- What is the best case scenario for binary search? Worst case scenario?
- Determine the runtime of the sequential search algorithm. What is the ratio of the time it takes to search the list and the size of the list?
- Determine the runtime of the binary search algorithm. What is the ratio of the time it takes to search the list and the size of the list? How does it compare with the sequential search?