Java分治法与二分搜索算法实例分析

Java分治法与二分搜索算法实例分析 - 完整攻略

分治法

分治法（Divide and Conquer）是一种算法设计思想，它将原问题分成若干个子问题，然后将子问题逐一分解、解决，最终将子问题的解合并得到原问题的解。

分治法一般包含三个步骤：分解原问题，解决子问题，合并子问题的解。具体实现时，一般采用递归结构。

下面是一个使用分治法的例子：在一个无序数组中查找最大值。

示例1：查找最大值

public class FindMax {

    public static int findMax(int[] arr, int leftIndex, int rightIndex) {

        if (leftIndex == rightIndex) {
            return arr[leftIndex]; // 如果只有一个元素，则直接返回该元素的值
        } else {
            int midIndex = (leftIndex + rightIndex) / 2;
            int leftMax = findMax(arr, leftIndex, midIndex); // 递归查找左半部分的最大值
            int rightMax = findMax(arr, midIndex + 1, rightIndex); // 递归查找右半部分的最大值
            return Math.max(leftMax, rightMax); // 返回左右两部分中的最大值
        }
    }

    public static void main(String[] args) {
        int[] arr = {3, 9, 6, 8, 2, 3, 7};
        int max = findMax(arr, 0, arr.length - 1);
        System.out.println("最大值为：" + max);
    }
}

该示例通过递归将原问题分解为两个子问题，然后通过递归解决子问题，并将子问题的解合并得到原问题的解。

二分搜索算法

二分搜索算法（Binary Search）是一种基于分治思想的搜索算法，用于在有序数列中查找目标值。

二分搜索算法的实现思路是：从数列的中间开始比较，如果目标值比中间值小，则在数列的左半部分继续查找，否则在数列的右半部分继续查找，重复这个过程，直到找到目标值或者查找完整个数列（即目标值不存在于数列中）。

下面是一个使用二分搜索算法的例子：在一个有序数组中查找目标值。

示例2：查找目标值

public class BinarySearch {

    public static int binarySearch(int[] arr, int target) {

        int leftIndex = 0;
        int rightIndex = arr.length - 1;

        while (leftIndex <= rightIndex) { // 当时刻左右指针没有重合时，继续查找目标值

            int midIndex = (leftIndex + rightIndex) / 2; // 计算中间元素的下标

            if (target == arr[midIndex]) {
                return midIndex; // 如果目标值等于中间元素，直接返回中间元素的下标
            } else if (target < arr[midIndex]) {
                rightIndex = midIndex - 1; // 如果目标值小于中间元素，继续在左半部分查找
            } else {
                leftIndex = midIndex + 1; // 如果目标值大于中间元素，继续在右半部分查找
            }
        }

        return -1; // 如果查找完整个数列，仍未找到目标值，返回-1
    }

    public static void main(String[] args) {
        int[] arr = {1, 3, 4, 5, 7, 8, 10};
        int target = 7;
        int index = binarySearch(arr, target);
        if (index != -1) {
            System.out.println("目标值在数组中的下标为：" + index);
        } else {
            System.out.println("数组中没有该目标值！");
        }
    }
}

该示例通过将数列分解为两个子问题，然后确定哪一部分可能包含目标值，并在找到目标值或者查找完整个数列后返回目标值的下标。