求助：Python递归实现二分查找定位目标数或首个更大数

Got it, let's break down how to implement this recursive binary search function that meets your requirements. The core idea is to narrow down the search range recursively until we either find the target or reach a single element to make our final decision.

Approach #

Following your specified steps, here's the refined recursive logic:

• Base Case: When the search range is reduced to a single element (start index equals end index):
  • If this element equals the target, return its index.
  • If this element is larger than the target, return its index (since it's the first larger element in the narrowed range).
  • If this element is smaller than the target, return start + 1 (because the target should be inserted after this element, which is the position of the first element larger than it if it existed, or the end of the list if all elements are smaller).
• Recursive Case:
  • Calculate the middle index of the current range.
  • If the target equals the middle element, return the middle index immediately.
  • If the target is smaller than the middle element, recursively search the left half (from start to middle - 1).
  • If the target is larger than the middle element, recursively search the right half (from middle + 1 to end).

Implementation Code #

def recursive_binary_search(nums, target, start=0, end=None):
    # Initialize end index if not provided
    if end is None:
        end = len(nums) - 1
    
    # Base case: single element left in range
    if start == end:
        if nums[start] == target:
            return start
        elif nums[start] > target:
            return start
        else:
            return start + 1
    
    # Calculate middle index
    mid = (start + end) // 2
    
    if nums[mid] == target:
        return mid
    elif target < nums[mid]:
        # Search left half
        return recursive_binary_search(nums, target, start, mid - 1)
    else:
        # Search right half
        return recursive_binary_search(nums, target, mid + 1, end)

Example Usage #

Let's test this function with some common scenarios to verify:

• Target exists in the list:

  nums = [1, 3, 5, 7, 9]
  print(recursive_binary_search(nums, 5))  # Output: 2 (correct position of 5)
  

• Target is smaller than some elements but not present:

  print(recursive_binary_search(nums, 4))  # Output: 2 (position of 5, first element larger than 4)
  

• Target is larger than all elements:

  print(recursive_binary_search(nums, 10))  # Output: 5 (insert position at the end of the list)
  

• Target is smaller than all elements:

  print(recursive_binary_search(nums, 0))  # Output: 0 (position of 1, first element larger than 0)
  

Key Notes #

• The function uses optional start and end parameters to track the current search range, which keeps the recursion clean without modifying the original list.
• The base case handles all edge scenarios: when the target isn't found, it correctly returns the position where the target would be inserted (which is exactly the first larger element's position, or the end of the list if all elements are smaller).
• Since the input list is ordered (as specified), binary search works efficiently with a time complexity of O(log n).

内容的提问来源于stack exchange，提问作者Jorge Luiz Garioli