Binary Search and the struggle of math.
Learning algorithms and the math behind them can be a challenging task, but the reward of understanding the underlying concepts and optimizing their performance is worth it. Let's take a look at the mathematics behind one of the simplest algorithms: the binary search.
The binary search algorithm is used to search for a specific value in a sorted array, the sorted part of very important. It starts by finding the middle value in the array and comparing it to the target value. If the middle value is equal to the target, the algorithm is complete. If the middle value is greater than the target, the algorithm continues the search in the left half of the array. If the middle value is less than the target, the algorithm continues the search in the right half of the array. This process is repeated until the target is found or the search space is empty.
The math behind the binary search algorithm involves the concept of logarithms. Put simply a logarithm function is the inverse of exponentiation and is used to determine the power to which a number must be raised in order to produce a given result. In the context of binary search, logarithms are used to calculate the number of steps required to reduce the search space in half. The logarithm of the size of the array (in base 2) gives us the number of steps required to find the target value. This logarithmic complexity is expressed in big O notation as O(log n), where n is the size of the array.
Recommended by LinkedIn
Big O notation is used to describe the upper bound of the growth of an algorithm's running time as the input size grows. It provides a way to compare the performance of different algorithms and to determine the best algorithm for a given problem. In the case of binary search, the logarithmic running time makes it an efficient algorithm for searching large arrays.
Understanding the math behind algorithms such as the binary search can help us to design more efficient solutions to complex problems. Although challenging, taking the time to delve into the underlying concepts and mathematical models is an important step towards mastering algorithms and optimizing their performance. Maybe I should consider switching my CS major to Mathematics.