Binary search is a powerful algorithm used to find the position of a target value within a sorted array. Its efficiency, with a time complexity of $O(\log n)$, makes it a staple in many computational applications. However, one of the subtle yet crucial aspects of implementing binary search correctly is its terminating condition. Understanding this condition is key to ensuring the algorithm functions as intended without running into infinite loops or incorrect results.

Basic Concept of Binary Search

Binary search operates by repeatedly dividing the search interval in half. If the value of the search key is less than the item in the middle of the interval, the search continues in the lower half; otherwise, it continues in the upper half. This process is repeated until the key is found or the interval is empty.

Terminating Condition

The terminating condition of a binary search is generally the point at which the interval defined by the pointers `low` and `high` collapses. When the search begins, `low` is initialized to the starting index of the array, and `high` is initialized to the ending index. The loop continues as long as `low` is less than or equal to `high`. If no match is found by the time `low` exceeds `high`, the target does not exist in the array.

Technical Explanation

The crucial line in the binary search loop is:

• The midpoint is typically calculated as:
• This prevents potential overflow that might occur with `(low + high) // 2`.
• If the middle element is less than the target:
• If the middle element is greater than the target:
• The loop exits when `low` exceeds `high`, indicating the target is not in the list.
• Calculate `mid = 2` (element: 5), `low = 3`, `high = 5`
• Calculate `mid = 4`, (element: 9), `low = 3`, `high = 3`
• Calculate `mid = 3`, (element: 7), Target Found!
• Infinite Loop: Occurs if the condition is improperly set, such as `while low < high`, which may lead to missing the last element check.
• Off-by-One Errors: Incorrect updates to `low` or `high` can skip relevant sections of the array.
  • Adjust conditions to find either the first or last occurrence of the target by tweaking updates to `low` and `high`.
  • Binary search logic can be applied to rotated sorted arrays with modifications to check which segment of the array the mid-element represents.