Search Algorithms

What is a search algorithm?

An algorithm used to find specific data within a structure such as an array, graph, or tree.

What are the two main types of search algorithms?

Linear search and binary search.

What is linear search?

A simple search algorithm that checks each element sequentially until the target is found.

What is the time complexity of linear search?

O(n)

What is binary search?

A divide-and-conquer search algorithm that repeatedly divides a sorted array to find the target.

What is the time complexity of binary search?

O(log n)

What are the requirements for binary search?

The input data must be sorted.

What is interpolation search?

An improved variant of binary search for uniformly distributed data.

What is the time complexity of interpolation search?

O(log log n) on average, O(n) worst-case.

What is jump search?

A search algorithm that jumps ahead by fixed steps and then performs linear search backward.

What is the time complexity of jump search?

O(√n)

What is exponential search?

Searches an unbounded or large sorted array by doubling the range and then using binary search.

What is the time complexity of exponential search?

O(log n)

What is ternary search?

A search algorithm that divides the array into three parts instead of two like binary search.

What is the time complexity of ternary search?

O(log₃ n), similar to binary search.

What is depth-first search (DFS)?

A graph traversal algorithm that explores as far as possible along each branch before backtracking.

What is breadth-first search (BFS)?

A graph traversal algorithm that explores all neighbors at the current depth before moving to the next level.

What data structure is used in DFS?

Stack (or recursion).

What data structure is used in BFS?

Queue

What is the time complexity of DFS and BFS?

O(V + E), where V = vertices and E = edges.

Is DFS better than BFS?

It depends on the use case; DFS uses less memory, BFS guarantees shortest path.

Which search algorithm guarantees the shortest path in unweighted graphs?

BFS

What is best-first search?

A search that explores a graph based on a given heuristic.

What is A* search algorithm?

An informed search algorithm that uses cost and heuristic to find the shortest path.

What is the formula used in A* search?

f(n) = g(n) + h(n), where g = cost to reach node, h = heuristic estimate to goal.

What is Dijkstra’s algorithm?

A shortest path algorithm for weighted graphs with non-negative weights.

What is the time complexity of Dijkstra's algorithm?

O(V²) or O((V + E) log V) with a priority queue.

What is Greedy Best-First Search?

A search that chooses the node that appears to be closest to the goal using only the heuristic.

Is A* complete and optimal?

Yes, if the heuristic is admissible and consistent.

What is a heuristic in search algorithms?

A technique to estimate the cost or distance from a node to the goal.

What is an admissible heuristic?

A heuristic that never overestimates the true cost to reach the goal.

What is uniform cost search?

A search algorithm that expands the least-cost node first, similar to Dijkstra’s algorithm.

Is BFS complete and optimal?

Yes, for unweighted graphs.

Is DFS complete and optimal?

Complete for finite graphs but not optimal.

What is iterative deepening DFS?

A combination of DFS and BFS that increases depth limit step by step.

What is the advantage of iterative deepening DFS?

It uses less memory like DFS and finds shortest paths like BFS.

Which search algorithm is best for unbounded tree search?

Iterative Deepening DFS

What is IDA* (Iterative Deepening A*)?

A memory-efficient version of A* that combines heuristic search with iterative deepening.

What is bidirectional search?

A search from both the start and the goal that meets in the middle.

What is the time complexity of bidirectional search?

O(b^d/2), where b = branching factor and d = depth.

What is the benefit of bidirectional search?

It significantly reduces the search space.

What is hashing in search?

Using a hash function to directly access data, providing near O(1) search time.

What is the average time complexity of hash table search?

O(1)

What is the worst-case time complexity of hash table search?

O(n), due to collisions.

What is binary search tree (BST) search?

A search in a tree where left child < parent < right child.

What is the time complexity of search in a balanced BST?

O(log n)

What is the worst-case time for BST search?

O(n), when the tree becomes skewed.

What is the time complexity of search in an AVL Tree or Red-Black Tree?

O(log n)

What is a trie (prefix tree)?

A tree used for efficient retrieval of strings based on their prefixes.

What is the time complexity for search in a trie?

O(L), where L is the length of the string.

What is the main use of trie?

Autocomplete and spell-checking.

What is a linear probing in hash tables?

A collision resolution method where next available slot is checked sequentially.

What is binary search not suitable for?

Unsorted data or dynamic lists with frequent insertions.

What is a sentinel in search algorithms?

A dummy value used to simplify loop termination in linear search.

What is the difference between BFS and DFS in terms of completeness?

BFS is complete; DFS may not terminate in infinite-depth graphs.

Which search is better for memory-limited environments?

DFS or Iterative Deepening DFS.

Which search is better when goal is deep in the graph?

DFS

Which search is better when goal is close to root?

BFS