二分查找、分治、动态规划、KMP、贪心总结_分治 二分 dfs 动态规划 贪心

二分查找算法（包括二分递归查找和二分不递归查找）

package com.algorithm.binarysearch.binarysearchnorecur;

import java.lang.reflect.Array;
import java.util.ArrayList;

public class BinarySearchNoRecur {
   
    public static void main(String[] args) {
   
        int[] arr = {
   1, 3, 8, 10, 11, 67, 100};
        int index = binarySearchNoRecur(arr, 1);
        System.out.println(index);
        int index1 = binarySearchRecur(arr, 0, arr.length, 8);
        System.out.println(index1);
    }
    //二分查找非递归实现

    /**
     * @param arr    待查找的数组,这里的数组arr是升序排列
     * @param target 需要查找的数
     * @return 返回对应下标， -1表示没有找到
     */
    public static int binarySearchNoRecur(int[] arr, int target) {
   
        int left = 0;
        int right = arr.length - 1;
        while (left <= right) {
   //说明可以继续查找
            int mid = (left + right) / 2;
            if (arr[mid] == target) {
   
                return mid;
            } else if (arr[mid] > target) {
   
                right = mid - 1;
            } else {
   
                left = mid + 1;
            }
        }
        return -1;
    }

    //二分查找递归方法
    public static int binarySearchRecur(int[] arr, int left, int right, int target) {
   
        if (left > right) {
   
            return -1;
        }
        int mid = (left + right) / 2;
        if (arr[mid] > target) {
   
            return binarySearchRecur(arr, left, mid - 1,target);
        }else if (arr[mid] < target) {
   
            return binarySearchRecur(arr, mid + 1, right, target);
        }else {
   
            return mid;
        }
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65

分治算法

package com.algorithm.divideandconquer;

/*
汉诺塔思路：即分治算法思路
1、如果只有一个盘n = 1，直接 A -> C
2、如果n >= 2,总是看做两个盘，即最下面的一个盘和上面的所有盘，分为3步：
2.1、先将最上面的盘 A -> B
2.2、把最下面的 A -> C
2.3、把B中的所有盘移动到C

 */

public class Hanoitower {
   
    public static void main(String[] args) {
   
        hanoiTwoer(5, 'A', 'B', 'C');
    }

    //汉诺塔的移动方法
    //使用分治算法
    public static void hanoiTwoer(int nums, char a, char b, char c) {
   
        //如果只有一个盘
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24