Search

Search is a fundamental operation in computer science that involves finding a specific element or value within a data structure. There are various search algorithms, each with its own advantages and disadvantages depending on the context and the type of data structure being used. Some common search algorithms include:

  1. Linear Search: This algorithm checks each element in the data structure sequentially until it finds the target element or reaches the end of the structure. It has a time complexity of O(n).
  2. Binary Search: This algorithm works on sorted data structures. It repeatedly divides the search interval in half until it finds the target element or determines that it is not present. It has a time complexity of O(log n).
  3. Hashing: This technique uses a hash function to map keys to indices in a hash table. It allows for average-case O(1) time complexity for search operations, but can degrade to O(n) in the worst case due to collisions.
  4. Depth-First Search (DFS): This algorithm explores as far as possible along each branch before backtracking. It is commonly used in tree and graph data structures.
  5. Breadth-First Search (BFS): This algorithm explores all the neighbors at the present depth before moving on to the nodes at the next depth level. It is also used in tree and graph data structures.
  6. Interpolation Search: This algorithm is an improvement over binary search for uniformly distributed data. It estimates the position of the target element based on the values at the low and high indices. It has a time complexity of O(log log n) in the best case.
  7. Exponential Search: This algorithm is used for unbounded or infinite lists. It starts with a small range and exponentially increases the range until it finds an element greater than the target, then it performs a binary search on the identified range. It has a time complexity of O(log n).
  8. Topological Search: This algorithm is used for directed acyclic graphs (DAGs) to find a linear ordering of vertices such that for every directed edge uv from vertex u to vertex v, u comes before v in the ordering.

Choosing the appropriate search algorithm depends on factors such as the size of the data structure, whether it is sorted or not, and the specific requirements of the application.

Linear Search

1
2
3
4
5
def linear_search(arr, target):
    for i in range(len(arr)):
        if arr[i] == target:
            return i  # Return the index of the target element
    return -1  # Return -1 if the target element is not found

Binary Search

1
2
3
4
5
6
7
8
9
10
11
def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = left + (right - left) // 2
        if arr[mid] == target:
            return mid  # Return the index of the target element
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1  # Return -1 if the target element is not found

Hashing

1
2
3
4
5
6
7
8
9
class HashTable:
    def __init__(self):
        self.table = {}
    
    def insert(self, key, value):
        self.table[key] = value
    
    def search(self, key):
        return self.table.get(key, None)  # Return None if the key is not found

Depth-First Search (DFS)

1
2
3
4
5
6
7
8
def dfs(graph, start, visited=None):
    if visited is None:
        visited = set()
    visited.add(start)
    print(start)  # Process the current node
    for neighbor in graph[start]:
        if neighbor not in visited:
            dfs(graph, neighbor, visited)

Breadth-First Search (BFS)

1
2
3
4
5
6
7
8
9
10
11
12
13
from collections import deque
def bfs(graph, start):
    visited = set()
    queue = deque([start])
    visited.add(start)
    
    while queue:
        vertex = queue.popleft()
        print(vertex)  # Process the current node
        for neighbor in graph[vertex]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

Interpolation Search

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def interpolation_search(arr, target):
    low, high = 0, len(arr) - 1
    while low <= high and target >= arr[low] and target <= arr[high]:
        if low == high:
            if arr[low] == target:
                return low
            return -1
        
        pos = low + ((high - low) // (arr[high] - arr[low]) * (target - arr[low]))
        
        if pos < low or pos > high:
            return -1
        
        if arr[pos] == target:
            return pos
        elif arr[pos] < target:
            low = pos + 1
        else:
            high = pos - 1
    return -1

Exponential Search

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def exponential_search(arr, target):
    if arr[0] == target:
        return 0
    i = 1
    while i < len(arr) and arr[i] <= target:
        i *= 2
    return binary_search(arr, target, i // 2, min(i, len(arr) - 1))

def binary_search(arr, target, left, right):
    while left <= right:
        mid = left + (right - left) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

Topological Search

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def topological_sort(graph):
    visited = set()
    stack = []
    
    def dfs(vertex):
        visited.add(vertex)
        for neighbor in graph[vertex]:
            if neighbor not in visited:
                dfs(neighbor)
        stack.append(vertex)  # Add vertex to stack after visiting all neighbors
    
    for vertex in graph:
        if vertex not in visited:
            dfs(vertex)
    
    return stack[::-1]  # Return the reverse of the stack as the topological order

In conclusion, search algorithms are essential for efficiently retrieving information from data structures. The choice of algorithm depends on the specific use case, the structure of the data, and the performance requirements of the application. Understanding the strengths and weaknesses of each search algorithm can help in selecting the most appropriate one for a given problem.