Numerical Algorithms:

Binary Search:

• Efficient search algorithm for sorted arrays.

def binary_search(arr, target):
    """
    Perform binary search to find the index of the target in the sorted array arr.
    Returns the index of the target if found, otherwise returns -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
    
    # Target is not present in the array
    return -1

# Example usage:
arr = [2, 3, 4, 10, 40]
target = 10

result = binary_search(arr, target)

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

Explanation:

1. binary_search(arr, target):
   • This function implements the binary search algorithm to find the index of target in the sorted array arr.
   • It initializes low to the beginning of the array (0) and high to the end of the array (len(arr) - 1).
   • It iteratively divides the search interval in half (low to high) until the target is found or the interval is empty (low > high).
   • If the target matches the middle element (arr[mid]), it returns mid.
   • If the target is less than arr[mid], it narrows the search to the left half (high = mid - 1).
   • If the target is greater than arr[mid], it narrows the search to the right half (low = mid + 1).
   • If the target is not found after the loop, it returns -1.
2. Example Usage:
   • In the example provided, arr is [2, 3, 4, 10, 40] and target is 10.
   • The binary search algorithm finds 10 in arr and returns its index (3).

Binary Search for Lists

• works directly with lists because they are inherently ordered based on index.

def binary_search_list(sorted_list, target):
    """
    Perform binary search on a sorted list to find the index of the target.
    Returns the index of the target if found, otherwise returns -1.
    """
    low = 0
    high = len(sorted_list) - 1

    while low <= high:
        mid = (low + high) // 2

        if sorted_list[mid] == target:
            return mid
        elif sorted_list[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    
    return -1

# Example usage with a sorted list:
sorted_list = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
target = 23

result = binary_search_list(sorted_list, target)

if result != -1:
    print(f"Element {target} is present at index {result} in the sorted list.")
else:
    print(f"Element {target} is not present in the sorted list.")

Binary Search for Dictionaries Searching by Keys

• typically need to sort the keys or values first before applying binary search. This assumes you are searching for a specific key or value based on your requirements.

def binary_search_dict_keys(dictionary, target_key):
    """
    Perform binary search on sorted dictionary keys to find the index of the target key.
    Returns the index of the target key if found, otherwise returns -1.
    """
    sorted_keys = sorted(dictionary.keys())
    low = 0
    high = len(sorted_keys) - 1

    while low <= high:
        mid = (low + high) // 2

        if sorted_keys[mid] == target_key:
            return mid
        elif sorted_keys[mid] < target_key:
            low = mid + 1
        else:
            high = mid - 1
    
    return -1

# Example usage with a dictionary:
dictionary = {'apple': 5, 'banana': 3, 'cherry': 7, 'date': 10, 'fig': 2}
target_key = 'cherry'

result = binary_search_dict_keys(dictionary, target_key)

if result != -1:
    print(f"Key '{target_key}' is present in the dictionary at index {result}.")
else:
    print(f"Key '{target_key}' is not present in the dictionary.")

Binary Search for Dictionaries Searching by Values

def binary_search_dict_values(dictionary, target_value):
    """
    Perform binary search on sorted dictionary values to find the index of the target value.
    Returns the index of the target value if found, otherwise returns -1.
    """
    sorted_items = sorted(dictionary.items(), key=lambda x: x[1])
    sorted_values = [item[1] for item in sorted_items]
    low = 0
    high = len(sorted_values) - 1

    while low <= high:
        mid = (low + high) // 2

        if sorted_values[mid] == target_value:
            return mid
        elif sorted_values[mid] < target_value:
            low = mid + 1
        else:
            high = mid - 1
    
    return -1

# Example usage with a dictionary:
dictionary = {'apple': 5, 'banana': 3, 'cherry': 7, 'date': 10, 'fig': 2}
target_value = 7

result = binary_search_dict_values(dictionary, target_value)

if result != -1:
    print(f"Value '{target_value}' is present in the dictionary at index {result}.")
else:
    print(f"Value '{target_value}' is not present in the dictionary.")

Newton-Raphson Method:

• Iterative method for finding successively better approximations to the roots (or zeroes) of a real-valued function.

:(