Search & Backtracking
Introduction to Searching
Searching algorithms find specific elements within data structures. The choice of algorithm depends on whether the data is sorted, the data structure type, and performance requirements.
Linear Search
Linear search checks each element sequentially until the target is found or the list ends. Time complexity: O(n), works on both sorted and unsorted data.
Linear Search Implementation
#include <iostream>
#include <vector>
using namespace std;
int linearSearch(const vector<int>& arr, int target) {
for (int i = 0; i < arr.size(); i++) {
if (arr[i] == target) {
return i;
}
}
return -1; // Not found
}
int main() {
vector<int> arr = {64, 34, 25, 12, 22, 11, 90};
int target = 22;
int result = linearSearch(arr, target);
if (result != -1) {
cout << "Element " << target << " found at index " << result << endl;
} else {
cout << "Element " << target << " not found" << endl;
}
return 0;
}Linear search iterates through each element until target is found.
Binary Search
Binary search works on sorted arrays by repeatedly dividing the search interval in half. Time complexity: O(log n), much faster than linear search for large datasets.
Binary Search Implementation
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int binarySearch(const vector<int>& arr, int target) {
int left = 0, right = arr.size() - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == target) {
return mid;
}
if (arr[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1; // Not found
}
int main() {
vector<int> arr = {11, 12, 22, 25, 34, 64, 90};
int target = 25;
int result = binarySearch(arr, target);
if (result != -1) {
cout << "Element " << target << " found at index " << result << endl;
} else {
cout << "Element " << target << " not found" << endl;
}
return 0;
}Binary search divides the array in half at each step, eliminating half of the remaining elements.
Depth-First Search (DFS)
DFS explores as far as possible along each branch before backtracking. Useful for tree/graph traversal, maze solving, and finding connected components.
DFS Implementation
#include <iostream>
#include <vector>
#include <stack>
using namespace std;
class Graph {
private:
int V;
vector<vector<int>> adj;
public:
Graph(int vertices) : V(vertices) {
adj.resize(V);
}
void addEdge(int v, int w) {
adj[v].push_back(w);
}
// Recursive DFS
void DFSUtil(int v, vector<bool>& visited) {
visited[v] = true;
cout << v << " ";
for (int neighbor : adj[v]) {
if (!visited[neighbor]) {
DFSUtil(neighbor, visited);
}
}
}
void DFS(int start) {
vector<bool> visited(V, false);
cout << "DFS traversal starting from vertex " << start << ": ";
DFSUtil(start, visited);
cout << endl;
}
// Iterative DFS using stack
void DFSIterative(int start) {
vector<bool> visited(V, false);
stack<int> stk;
stk.push(start);
cout << "Iterative DFS: ";
while (!stk.empty()) {
int v = stk.top();
stk.pop();
if (!visited[v]) {
visited[v] = true;
cout << v << " ";
// Add neighbors to stack (in reverse order)
for (int i = adj[v].size() - 1; i >= 0; i--) {
if (!visited[adj[v][i]]) {
stk.push(adj[v][i]);
}
}
}
}
cout << endl;
}
};
int main() {
Graph g(7);
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 3);
g.addEdge(1, 4);
g.addEdge(2, 5);
g.addEdge(2, 6);
g.DFS(0);
g.DFSIterative(0);
return 0;
}DFS can be implemented recursively or iteratively using a stack.
Breadth-First Search (BFS)
BFS explores all neighbors at the current depth before moving to the next depth level. Excellent for finding shortest paths in unweighted graphs.
BFS Implementation
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
class Graph {
private:
int V;
vector<vector<int>> adj;
public:
Graph(int vertices) : V(vertices) {
adj.resize(V);
}
void addEdge(int v, int w) {
adj[v].push_back(w);
}
void BFS(int start) {
vector<bool> visited(V, false);
queue<int> q;
visited[start] = true;
q.push(start);
cout << "BFS traversal starting from vertex " << start << ": ";
while (!q.empty()) {
int v = q.front();
q.pop();
cout << v << " ";
for (int neighbor : adj[v]) {
if (!visited[neighbor]) {
visited[neighbor] = true;
q.push(neighbor);
}
}
}
cout << endl;
}
// Find shortest path using BFS
void shortestPath(int start, int target) {
vector<bool> visited(V, false);
vector<int> parent(V, -1);
queue<int> q;
visited[start] = true;
q.push(start);
while (!q.empty()) {
int v = q.front();
q.pop();
if (v == target) {
// Reconstruct path
vector<int> path;
int current = target;
while (current != -1) {
path.push_back(current);
current = parent[current];
}
cout << "Shortest path from " << start << " to " << target << ": ";
for (int i = path.size() - 1; i >= 0; i--) {
cout << path[i];
if (i > 0) cout << " -> ";
}
cout << endl;
return;
}
for (int neighbor : adj[v]) {
if (!visited[neighbor]) {
visited[neighbor] = true;
parent[neighbor] = v;
q.push(neighbor);
}
}
}
cout << "No path found from " << start << " to " << target << endl;
}
};
int main() {
Graph g(7);
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 3);
g.addEdge(1, 4);
g.addEdge(2, 5);
g.addEdge(2, 6);
g.addEdge(3, 6);
g.BFS(0);
g.shortestPath(0, 6);
return 0;
}BFS uses a queue to explore nodes level by level, guaranteeing shortest path in unweighted graphs.