Java 折半查找算法：递归和迭代实现

以下是 Java 中使用折半查找法的代码示例：

public class BinarySearch {
    // 递归实现折半查找
    public static int binarySearchRecursive(int[] arr, int target) {
        return binarySearchRecursive(arr, target, 0, arr.length - 1);
    }

    private static int binarySearchRecursive(int[] arr, int target, int left, int right) {
        if (left > right) {
            return -1; // 目标元素不存在
        }
        
        int mid = left + (right - left) / 2;
        
        if (arr[mid] == target) {
            return mid; // 目标元素找到
        } else if (arr[mid] > target) {
            return binarySearchRecursive(arr, target, left, mid - 1); // 在左半部分继续查找
        } else {
            return binarySearchRecursive(arr, target, mid + 1, right); // 在右半部分继续查找
        }
    }

    // 非递归实现折半查找
    public static int binarySearchIterative(int[] arr, int target) {
        int left = 0;
        int right = arr.length - 1;
        
        while (left <= right) {
            int mid = left + (right - left) / 2;
            
            if (arr[mid] == target) {
                return mid; // 目标元素找到
            } else if (arr[mid] > target) {
                right = mid - 1; // 在左半部分继续查找
            } else {
                left = mid + 1; // 在右半部分继续查找
            }
        }
        
        return -1; // 目标元素不存在
    }

    public static void main(String[] args) {
        int[] arr = {1, 3, 5, 7, 9};
        int target = 5;
        
        int index = binarySearchRecursive(arr, target);
        System.out.println('目标元素的索引为（递归实现）：' + index);
        
        index = binarySearchIterative(arr, target);
        System.out.println('目标元素的索引为（非递归实现）：' + index);
    }
}

该代码实现了两种折半查找法：递归实现和非递归实现。在给定的有序数组中查找目标元素，并返回其索引值。如果目标元素不存在于数组中，则返回-1。