分治算法基础

应用场景

一个问题可以分解为若干个规模较小的相同问题，且各个子问题是相互独立的，且解决子问题后就可以解决这个问题，这样的情况可以使用分治思维。

递归二分查找

static int binSearch(int[] arrays, int target, int low, int high) {
        if (low == high) {
            return target == arrays[low] ? low : -1;
        }
        int binIndex = (low + high) / 2;
        if (arrays[binIndex] < target) {
            return binSearch(arrays, target, binIndex + 1, arrays.length - 1);
        } else if ((arrays[binIndex] > target)) {
            return binSearch(arrays, target, 0, binIndex);
        } else return binIndex;
    }

非递归二分查找

static int binSearch(int[] array, int left, int right, int target) {
        // 如果上边界大于等于下边界
        while (left <= right) {
            // 求出二分后的中间索引
            int halfIndex = (right + left) / 2;
            // 中间值等于目标值，直接返回索引
            if (array[halfIndex] == target) {
                return halfIndex;
            }
            // 目标值小于中间值，上边界改为中间索引-1
            else if (target < array[halfIndex]) {
                right = halfIndex - 1;
            }
            // 目标值大于中间值，下边界改为中间索引+1
            else if (target > array[halfIndex]) {
                left = halfIndex + 1;
            }
        }
        return -1;
    }

归并排序

public static int[] mergeSort(int[] array) {
    if (array.length <= 1) {
        return array;
    }
    // 拆分数组
    int binIndex = array.length / 2;
    int[] left = Arrays.copyOfRange(array, 0, binIndex);
    int[] right = Arrays.copyOfRange(array, binIndex, array.length);
    // 分解+合并
    return merge(mergeSort(left), mergeSort(right));
}

public static int[] merge(int[] left, int[] right) {
    int l = 0, r = 0; // 代表左右连个数组的指针
    int[] mergeArray = new int[left.length + right.length];
    for (int i = 0; i < mergeArray.length; i++) {
        if (l >= left.length) mergeArray[i] = right[r++];
        else if (r >= right.length) mergeArray[i] = left[l++];
        else if (left[l] < right[r]) mergeArray[i] = left[l++];
        else mergeArray[i] = right[r++];
    }
    return mergeArray;
}

判断回文字符串

def isPal(s):
    if len(s) <= 1:
        return True
    else:
        return s[0]==s[-1] and isPal(s[1:-1])