The binary search algorithm is an efficient method for finding a target value within a sorted array or list. It works by repeatedly dividing the search interval in half. If the target value 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.

Python Implementation

def binary_search(arr, target):
    """
    Performs binary search on a sorted array to find the index of the target element.

    Parameters:
    arr (list): A list of sorted elements.
    target (Any): The element to search for.

    Returns:
    int: The index of the target element if found; otherwise, -1.
    """
    left, right = 0, len(arr) - 1

    while left <= right:
        mid = left + (right - left) // 2  # Avoids potential overflow

        # Check if target is present at mid
        if arr[mid] == target:
            return mid
        # If target is greater, ignore left half
        elif arr[mid] < target:
            left = mid + 1
        # If target is smaller, ignore right half
        else:
            right = mid - 1

    # Target was not found in the array
    return -1

# Example usage
if __name__ == "__main__":
    sorted_list = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
    target = 5
    result = binary_search(sorted_list, target)

    if result != -1:
        print(f"Element found at index: {result}")
    else:
        print("Element not found in the array.")

Program Structure Explanation

• Function Definition: The function binary_search(arr, target) takes a sorted array arr and a target value to find.
• Initialization: Two pointers, left and right, are initialized to represent the current search bounds.
• While Loop: The loop continues as long as left is less than or equal to right. Within the loop:
  • Mid Calculation: The middle index is calculated to split the search interval.
  • Comparison: If the middle element matches the target, the index is returned. If the target is larger, the search continues in the upper half. If smaller, it continues in the lower half.
• Return Value: If the target is not found, the function returns -1.

Example Usage

The example demonstrates how to use the binary_search function. A sorted list and a target value are defined, and the result is printed based on whether the target was found.