Search Algorithms Flashcards
Search Algorithms
Search algorithms are techniques for finding specific elements within a data structure or collection. Examples include Binary Search, Depth-First Search (DFS), and Breadth-First Search (BFS).
Binary Search
Binary Search is an efficient search algorithm used to find a specific element in a sorted array or list. It works by repeatedly dividing the search interval in half and comparing the target element with the middle element of the interval. This process continues until the element is found or it is determined that the element is not in the list. Binary Search has a time complexity of O(log n).
Depth-First Search (DFS)
Depth-First Search (DFS) is a graph traversal algorithm that explores as far as possible along each branch before backtracking. It starts from a source node and explores all its adjacent nodes before moving deeper into the graph. DFS can be implemented using recursion or a stack data structure. It is often used for tasks like determining connected components and detecting cycles in graphs.
Breadth-First Search (BFS)
Breadth-First Search (BFS) is a graph traversal algorithm that explores all the vertices at the current level before moving to the next level. It starts from a source node and explores all its neighbors before moving to the neighbors’ neighbors. BFS is commonly used to find the shortest path in unweighted graphs, and it can also be used for tasks like level-order traversal of trees and finding connected components in graphs.
