Search Algorithms

While sorting algorithms focus on how to sort an entire list of elements, search algorithms intend to find an element that matches the search conditions, and we choose different algorithms depending on the type of data or data structure.

Binary search algorithm

Binary search is a classic “divide and conquer” search algorithm that can be implemented recursively. Given a sorted list, binary search starts by comparing the item in the middle of the list and explores either the left or right side depending on the result, and then repeats the process until the desired item is found (or not).

Pattern search: Knuth–Morris–Pratt

Pattern searching in text, or substring search, is a common problem. One of the most famous algorithms for solving this problem is the Knuth-Morris-Pratt algorithm (KMP). It works by searching for the given pattern over the input text and backtracking efficiently to the next possible starting place, resulting in a O(N) worst case runtime.