Understanding binary search algorithm

The strategy from the earlier example could be used to create an algorithm. To explain this algorithm, we will use an array sorted in ascending order and search for a target number.

Algorithm

The binary search algorithm searches for a target value in a sorted array by repeatedly dividing the search space in half. It works by comparing the target value with the middle element of the current search range. The algorithm begins by initialising two indices that define the current search range in which the target value may exist.

`low` is set to the first index of the array i.e `0`.

`high` is set to the last index of the array i.e `arr.size() - 1`.

Initialize the low and high indices

The algorithm enters a loop that continues as long as low <= high. This condition ensures that there are still elements remaining in the search range that could potentially match the target value.

Why do we continue while low <= high?

When low becomes greater than high, it means the search range is empty, and all possible positions have already been checked. At this point, the target value cannot be present in the array.