# Algorithms

Well, algorithm is not a separated concept from data structure, and some algorithms have been covered in the above section. Here I’ll just list some more.

## Sort

For sorting algorithms, refer to my GitHub post. The post currently includes insertion sort, merge sort and quick sort.

Given a sorted array, binary search could find the target with a time complexity of $O(n)$. Following is the basic template:

The pointer `left` and `right` are used to control the search area.
If the middle value equals our target, then we just make it. If the middle value is less than the target, then it means that we should search the larger part. We need to move the left pointer to right. Otherwise, we need to move the right pointer to left if the middle value is greater.
Note that the calculation of mid is a bit counterintuitive. The purpose is to prevent the overflow caused by adding. Suppose that left is 1 and right is INT_MAX, then the adding will cause overflow and lead to errors. Therefore, it’s advised to use `left + (right - left) / 2` instead.