Binary search is a classic algorithm in computer science that efficiently finds a target value within a sorted array. The central principle of the binary search is divide-and-conquer, where the array is continually divided into halves until the target value is found or the search space is reduced to zero.

The Binary Search Algorithm:

Here’s a basic version of the binary search algorithm:

1. Initialize Pointers: Start with two pointers, lo (low) and hi (high), which represent the beginning and end of the array.
2. Midpoint Calculation: Calculate the middle index, often using lo + (hi - lo) / 2 .
3. Comparison: Compare the middle element with the target value.
   • If it equals the target, return the middle index.
   • If it is less than the target, move the lo pointer to mid + 1 .
   • If it is greater, move the hi pointer to mid - 1 .
4. Repeat: Continue this process until the target is found or the search space is empty (lo > hi ).

Why Use lo + (hi - lo) / 2

?

A common mistake when implementing the binary search is to calculate the midpoint as mid = (lo + hi) / 2 . However, this can lead to potential overflow errors if lo and hi are large integers. Let’s break down why lo + (hi - lo) / 2 is the preferred method:

Avoiding Overflow:

• When lo and hi are large, their sum can exceed the maximum value representable by an integer data type, causing overflow and incorrect results.
• Instead, using lo + (hi - lo) / 2 ensures that we are always working within the bounds of the array’s size, thus preventing overflow.

Example:

For an array of size 10 million with lo = 0 and hi = 9,999,999 :

• Using mid = (lo + hi) / 2 would lead to 5,000,000 which is correct, but risky upon reaching larger limits.
• Using mid = lo + (hi - lo) / 2 calculates mid as 0 + (9,999,999 - 0) / 2 which simplifies directly to 5,000,000 . This avoids the risk of overflow.

Additional Considerations:

• Integer Division: Note that division in an integer context rounds towards zero in many programming languages, which is suitable for indices.
• Performance: The binary search runs in $O(\log n)$ time complexity, making it highly efficient for large arrays, provided they are sorted.

Implementation Example:

Below is an implementation of binary search in Python: