Binary Search with a List

• Efficient O(log n) search algorithm for sorted arrays/list that repeatedly divides the search interval in half.
• Divides the search space in half with each iteration.
• Much faster than linear search for sorted data.

def binary_search(arr, target):
    """
    find the index of target in arr.
    Return the index if found, otherwise return -1.
    """
    low = 0
    high = len(arr) - 1
    
    while low <= high:
        mid = (low + high) // 2
        
        # Check if target is present at mid
        if arr[mid] == target:
            return mid
        # If target is greater, ignore left half
        elif arr[mid] < target:
            low = mid + 1
        # If target is smaller, ignore right half
        else:
            high = mid - 1
    
    # If we reach here, the target is not in the list
    return -1

# Example usage:
arr = [5, 8, 12, 17, 23, 45, 67]
target = 23
result = binary_search(arr, target)

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

Why Use a Sorted List for Binary Search:

• Efficiency: Binary search is significantly faster than linear search, with a time complexity of O(log n), where n is the number of elements. This efficiency is achievable because binary search can quickly narrow down the search space by comparing the target value with the middle element of the list.
• Guaranteed Performance: Binary search relies on the property of sorted lists where elements are already ordered. This ensures that the algorithm can efficiently determine whether the target exists and where it might be located.
• Ease of Implementation: Implementing binary search in a sorted list is straightforward due to the ability to access elements by index and the ordered nature of the data.

Step 1: Function Definition: The binary_search function takes two parameters: arr (the sorted list to be searched) and target (the element to search for).

Step 2: Initialization: Initialize two pointers, low and high, to represent the search range within the list. Initially, low is set to 0 and high is set to len(arr) - 1.

Step 3: While Loop: The loop continues as long as low is less than or equal to high.

Step 4: Middle Index: Calculate the middle index (mid) as the integer division of (low + high) // 2.

Step 5: Comparison:

• If the element at mid is equal to target, return mid (the index of the target element).
• If the element at mid is less than target, update low to mid + 1 to search in the right half of the list.
• If the element at mid is greater than target, update high to mid - 1 to search in the left half of the list.

Step 6: Return Statement: If the loop exits without finding the target, return -1 to indicate that the target is not in the list.

def binary_search(arr, target):
    # Initialize the low and high pointers
    low = 0
    high = len(arr) - 1
    
    # While the search space is valid
    while low <= high:
        # Find the middle index
        mid = (low + high) // 2
        
        # Check if the target is at the mid index
        if arr[mid] == target:
            return mid
        # If the target is greater than the mid element, ignore the left half
        elif arr[mid] < target:
            low = mid + 1
        # If the target is less than the mid element, ignore the right half
        else:
            high = mid - 1
    
    # Return -1 if the target is not found
    return -1

# Example usage:
arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
target = 7
result = binary_search(arr, target)
if result != -1:
    print(f"Element {target} found at index {result}")
else:
    print(f"Element {target} not found in the list")