Design a function that implements binary search on a sorted array of integers.
- User
Design a function that implements binary search on a sorted array of integers.
Assistant
Okay, here is a Python function design for binary search on a sorted array of integers.
def binary_search(sorted_arr, target): """ Performs binary search on a sorted array of integers to find the index of a target value. Args: sorted_arr: A list or tuple of integers, sorted in ascending order. target: The integer value to search for within the array. Returns: The index of the target value in the array if found. -1 if the target value is not present in the array. """ low = 0 high = len(sorted_arr) - 1 # Loop continues as long as the search space is valid (low index is not past high index) while low <= high: # Calculate the middle index. # Using low + (high - low) // 2 prevents potential integer overflow # compared to (low + high) // 2 for very large arrays/indices. mid = low + (high - low) // 2 # Get the value at the middle index mid_value = sorted_arr[mid] # Check if the middle value is the target if mid_value == target: return mid # Target found at index mid # If the target is greater than the middle value, search the right half elif target > mid_value: low = mid + 1 # Adjust the low boundary to mid + 1 # If the target is smaller than the middle value, search the left half else: # target < mid_value high = mid - 1 # Adjust the high boundary to mid - 1 # If the loop finishes without returning, the target was not found return -1 # --- Example Usage --- my_array = [2, 5, 7, 8, 11, 12, 15, 19, 22, 25] # Test case 1: Target is present target1 = 12 index1 = binary_search(my_array, target1) print(f"Searching for {target1}: Found at index {index1}") # Output: Searching for 12: Found at index 5 # Test case 2: Target is not present target2 = 10 index2 = binary_search(my_array, target2) print(f"Searching for {target2}: Found at index {index2}") # Output: Searching for 10: Found at index -1 # Test case 3: Target is the first element target3 = 2 index3 = binary_search(my_array, target3) print(f"Searching for {target3}: Found at index {index3}") # Output: Searching for 2: Found at index 0 # Test case 4: Target is the last element target4 = 25 index4 = binary_search(my_array, target4) print(f"Searching for {target4}: Found at index {index4}") # Output: Searching for 25: Found at index 9 # Test case 5: Empty array empty_array = [] target5 = 5 index5 = binary_search(empty_array, target5) print(f"Searching for {target5} in empty array: Found at index {index5}") # Output: Searching for 5 in empty array: Found at index -1Explanation:
- Initialization:
lowis initialized to0, representing the start index of the search space.highis initialized tolen(sorted_arr) - 1, representing the end index of the search space.
- Loop Condition:
- The
while low <= high:loop continues as long as the search space is valid. Iflowbecomes greater thanhigh, it means the target is not in the array.
- The
- Finding the Middle:
mid = low + (high - low) // 2calculates the middle index. This method is preferred over(low + high) // 2to avoid potential integer overflow issues in languages with fixed-size integers, although it's less critical in standard Python implementations due to arbitrary-precision integers. It's still good practice.
- Comparison:
- The value at the middle index (
sorted_arr[mid]) is compared with thetarget. - If
mid_value == target, the target is found, and its indexmidis returned. - If
target > mid_value, the target must be in the right half of the current search space (if it exists). So, we discard the left half by updatinglowtomid + 1. - If
target < mid_value, the target must be in the left half of the current search space (if it exists). So, we discard the right half by updatinghightomid - 1.
- The value at the middle index (
- Target Not Found:
- If the
whileloop completes without finding the target (i.e.,lowbecomes greater thanhigh), the function returns-1to indicate that the target is not present in the array.
- If the
Key Requirement: This function relies heavily on the input array
sorted_arrbeing sorted in ascending order. If the array is not sorted, the results will be unpredictable and incorrect.- Initialization:
Other models, same or similar prompt
Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.