Linear SearchConcept

Iterate through the array and compare each element to the target element until found

Runtime

O(n)

Video Explanation

‍

Binary Search

Concept

Pick a middle point and determine which direction to look for the target, repeat the process on that side of the array (Note: only works for a fully-sorted array)

Runtime

O(lgn)

Video Explanation

Example Problems 

‍

Breadth-First Search

Concept

Srch a tree/graph, looking at the nodes closest to the start first

Implementation

Uses a Queue (FIFO) to search nodes found earlier before nodes found recently

Runtime

O(V+E)

Video Explanation

Example Problems

‍

Depth-First Search

Concept

Search a tree/graph, looking at the nodes furthest from the start first

Implementation

Uses a Stack (LIFO) to search nodes found recently before nodes found earlier

Runtime

O(V+E)

Video Explanation

Example Problems

‍

Dijkstra's Algorithm

Concept

Find the shortest path between two vertices in a graph

Implementation

Uses a Priority Queue to repeatedly select the nearest unvisited vertex and calculate the distance to all neighboring vertices (until the Goal is reached)

Runtime

O(V+E)

Video Explanation

‍

Topological Sort

Concept

Order a graph’s vertices (must be a Directed Acyclic Graph) so that for each directed edge <u,v>, u comes before v in the ordering

Implementation

Repeatedly search the graph for vertices with no incoming edges, add them to the ordering, and remove them from future consideration

Runtime

O(V+E)

Video Explanation

Interview Cake Explanation

A* SearchConcept

Improve on Dijkstra's by using heuristics to select the best path to explore next

Implementation

Uses a Priority Queue and some user-specified heuristic (straight line distance, Manhattan distance, etc.)

Runtime

O(V+E)

Video Explanation