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
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)
