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.
|Big O Complexity|
|search (sorted)||O(log 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
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