# 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.