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.
The time complexity of Binary Search is O(log n). This algorithm is quite famous. It is also often asked in a programming interview.