Snippet Code For Algorithm Implmentation

Here’s a well-structured and efficient implementation of the Binary Search algorithm in Python: ```python def binary_search(arr, target): """ Perform binary search on a sorted array to find the target element. Parameters: arr (list): A sorted list of elements where we need to search for the target. target (int/float): The element to search for in the array. Returns: int: The index of the target element in the array if found, otherwise -1. """ # Input validation if not isinstance(arr, list): raise ValueError("The first argument must be a list.") if not all(isinstance(x, (int, float)) for x in arr): raise ValueError("All elements in the array must be integers or floats.") # Define the initial search bounds left, right = 0, len(arr) - 1 while left <= right: # Find the middle index to split the array mid = left + (right - left) // 2 # This prevents potential overflow # Check if the middle element is the target if arr[mid] == target: return mid # If target is greater, ignore the left half elif arr[mid] < target: left = mid + 1 # If target is smaller, ignore the right half else: right = mid - 1 # Target is not present in the array return -1 # Example usage sorted_array = [1, 2, 4, 6, 8, 10, 12] target_element = 6 index = binary_search(sorted_array, target_element) print(f"Index of {target_element} in the array: {index}") # Output: Index of 6 in the array: 3 ``` ### Explanation: 1. **Function Definition and Parameters**: - The function `binary_search` takes two parameters: `arr`, which is a sorted list of elements, and `target`, the element we want to find. 2. **Input Validation**: - Check if `arr` is a list to prevent type errors. - Ensure all elements in `arr` are either integers or floats. 3. **Initialization**: - Initialize `left` to the start of the array (`0`) and `right` to the end (`len(arr) - 1`). 4. **Binary Search Logic**: - Use a `while` loop that continues as long as `left` is less than or equal to `right`. - Calculate the `mid` index to avoid overflow with `left + (right - left) // 2`. - Compare the middle element (`arr[mid]`) with the `target`: - If they are equal, return the `mid` index. - If `arr[mid]` is less than `target`, discard the left half by setting `left = mid + 1`. - If `arr[mid]` is greater than `target`, discard the right half by setting `right = mid - 1`. 5. **Element Not Found**: - If the loop ends without finding the `target`, return `-1`. ### Key Points: - **Time Complexity**: O(log n), where n is the number of elements in the array. This is because we reduce the search space by half with each iteration. - **Space Complexity**: O(1), as we are not using any additional space that scales with the input size. - **Edge Cases**: - The array is empty. - The target is less than the smallest element or greater than the largest element. - The target is at the first or last position in the array. ### Example Usage: The code includes an example usage to demonstrate how the function works. This prints the index of the target element `6` in the provided `sorted_array`, which is `3`.