What Is Binary Search and Why Is It Useful?

Problem:

Given a sorted array. Find x in the array.

You can approach the problem similar to above with binary search. You could approach the problem using the linear search - interate every element and find x in the array. However, it isn’t very efficient and will take forever if you have a long array. Therefore in that case, binary search is the way to go.

Here’s the step in the binary search:

1. Start with finding the midpoint of the array.
2. Compare the midpoint with the targeted number (x).
3. If midpoint is less than x, you know x is in the right side of the array after the midpoint.
4. If midpoint is greater than x, you know x is in the left side of the array before the midpoint.
5. Let’s say x is greater than the midpoint as appears in the example below. You know x is on the right side of the array, so you know to move the search to the right. You could do that by repeating the steps above, but this time narrow your search interval starting from the position next to mid (mid+1) to the end of the array.
6. Repeat the same steps as above until you find x, or until the interval is empty.

Example:

Reference:

https://www.geeksforgeeks.org/binary-search/