# Binary Search

I already cover some sorting algorithms here. Now, it's time to find an element within.

It is easy to find an element within a sorted list. If not, we need to check every element. Binary Search is a search algorithm within a sorted list. Here is how it works:

- Select an element in the middle.
- Check, whether it is lower or higher than the target.
- Narrow the portion to the right half if the middle is lower than the target.
- Otherwise, narrow it to the left half.
- Do it again repeatedly until the target is found.

This picture could help you to visualize the Binary Search.

An example in C.

int binary_search(int *list, int left, int right, int target) { if (right >= left) { int middle = left + (right - left) / 2; if (list[middle] == target) return middle; if (list[middle] < target) { return binary_search(list, middle + 1, right, target); } return binary_search(list, left, middle - 1, target); } return -1; }

The time complexity of Binary Search is O(log n). This algorithm is quite famous. It is also often asked in a programming interview.