Overview
Searching Algorithm, is one of the fundamental problems that people have been studying in the field
of Computer Science. The set of all possible solutions to a problem is called the search space.
Brutal-force searching method is the most intuitive method of searching through the
search space, whereas informed search algorithms use heuristics to apply
knowledge to the structure of the search space in order to reduce the amount
of time and space. The most straightforward searching algorithm is linear
search (or sequential search), simply scanning each element of the list (or
array) one after another, and producing a O(n) time efficiency. Hash table is
another kind of list search, requiring only constant time for search in the
average case, but more space overhead and terrible O(n) running time in the
worst-case.
A more sophisticated searching algorithm is Binary Search, which runs at O(h) time
on a tree of height h, where height is factor of log (n). This is significantly better
than linear search for large amount of data, but it requires the list to be sorted before
searching (see sorting algorithm ). Another type of searching algorithm is based on
specialized data structures, such as self-balancing tree structure, such as
red-black tree or AVL tress, and this type of search requires O(log n) time to
search.
Many of the problems in graph theory can be solved using search algorithms, such as
Breadth-first search , Depth-first search, or the infamous algorithm to find the
shortest route, Dijkstra’s algorithm, Kruskal’s algorithm, Prim’s algorithm for
instance.
Related Topics