Skip to content
TheChatArchiveThe Chat Archive
Geminigemini-2.5-flash-lite-preview-06-17-thinking· GoogleHugging Face LMArena Human Preference 140K

Design a function that implements binary search on a sorted array of integers.

From a Chatbot Arena battleThe same person sent this prompt to two anonymous models at once. Compare it with MiniMaxminimax-m1’s answer.
  1. User

    Design a function that implements binary search on a sorted array of integers.

  2. Gemini 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 -1
    

    Explanation:

    1. Initialization:
      • low is initialized to 0, representing the start index of the search space.
      • high is initialized to len(sorted_arr) - 1, representing the end index of the search space.
    2. Loop Condition:
      • The while low <= high: loop continues as long as the search space is valid. If low becomes greater than high, it means the target is not in the array.
    3. Finding the Middle:
      • mid = low + (high - low) // 2 calculates the middle index. This method is preferred over (low + high) // 2 to 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.
    4. Comparison:
      • The value at the middle index (sorted_arr[mid]) is compared with the target.
      • If mid_value == target, the target is found, and its index mid is 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 updating low to mid + 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 updating high to mid - 1.
    5. Target Not Found:
      • If the while loop completes without finding the target (i.e., low becomes greater than high), the function returns -1 to indicate that the target is not present in the array.

    Key Requirement: This function relies heavily on the input array sorted_arr being sorted in ascending order. If the array is not sorted, the results will be unpredictable and incorrect.

Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.