應用場景

一個問題可以分解為若干個規(guī)模較小的相同問題，且各個子問題是相互獨立的，且解決子問題后就可以解決這個問題，這樣的情況可以使用分治思維。

遞歸二分查找

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;
    }
    // 拆分數(shù)組
    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; // 代表左右連個數(shù)組的指針
    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])