Binary Search is a highly efficient search algorithm used to find the index of a target element in a sorted array. Unlike linear search which scans each cell costing O(n) time complexity, Binary Search divides the search boundaries in half each step, completing in O(log n) time complexity.

1. Divide and Conquer Concept

The core logic of binary search operates as follows:

  1. Define search boundaries using two pointer variables: low = 0 and high = len(array) - 1.
  2. Calculate the mid-point element: mid = low + (high - low) // 2.
  3. If array[mid] == target, return the mid index.
  4. If array[mid] < target, shift the lower boundary: low = mid + 1.
  5. If array[mid] > target, shift the upper boundary: high = mid - 1.

2. Preventing Integer Overflow

Critical Bug Check: Writing mid = (low + high) // 2 can trigger integer overflow in strictly typed languages (e.g. Java, C++) if the sum of low and high exceeds the 32-bit limits. Always use low + (high - low) // 2 instead!

3. Python Implementation Code

Here is a complete, working Python implementation of iterative binary search:

def binary_search(arr, target):
    low = 0
    high = len(arr) - 1
    
    while low <= high:
        # Prevent potential integer overflow
        mid = low + (high - low) // 2
        
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
            
    return -1  # Target not found

# Execution test
nums = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
target_val = 23
result_idx = binary_search(nums, target_val)

print("Target found at index:", result_idx) # Output: 5