# Searching and Binary Search

## Course launching August 2020

**Follow me on YouTube** for free coding interview videos.

Users who sign up for the email list will receive an exclusive 75% discount at launch.

Searching in interviews refers to finding an item in a data structure (and this item may or may not actually exist). In this article we'll be focusing on searching linear data structures like arrays, and then in the tree and graph sections, you'll expand on the concepts learned here binary search trees, depth first search, and breadth first search.

## Cheat Sheet

Big O Complexity | |
---|---|

search (sorted) | O(log n) |

search (unsorted) | O(n) |

**Searching in Interviews**

- Unique binary search examples (rotated array, sparse array, no max size)
- Compare multiple sorted arrays (ie. find median of two sorted arrays)
- Search a matrix
- Find duplicates

## Binary Search

Given an array, the most straightforward way to search it is linearly where you just look for an item.

(show linear search of sorted and then show how it can be improved).

This is O(n) time and would be no different for something like a string or linked list. You just pass over every item until you find it.

Binary search is basically searching with super powers and gives us *O(log n)* time.

The most important constraint for binary search to work: **the data must be sorted/order**.

Since it's ordered

Table of Contents