avatar
主页
计算机
金融
数学
关于
本站文章数 :
182
本站总字数 :
1318.0K
已运行天数 :
Kaka Wan Yifan
主页
计算机
金融
数学
关于
6.二分法
计算机算法入门经典(Java与Python描述)
字数总计:4.4K

上一章，我们多次提到二分插入排序，这是一个用二分法来找插入位置的插入排序算法。
但其实，我们最早一次提到二分法，是在《经典机器学习及其Python实现：9.决策树》，讨论信息熵的时候。

二分法的时间复杂度

当时，我们举了这么一个例子。

假设，现在有8个西瓜，而且8个西瓜中只有一个是好瓜。而我们对西瓜完全不了解，只能猜。这时候卖西瓜的和我们玩一个游戏，猜一次一块钱。
那么，成本最小的方式是：

graph LR 1-4{在1-4中?} 1-2{在1-2中?} 5-6{在5-6中?} 1{1?} 3{3?} 5{5?} 7{7?} g1(瓜-1) g2(瓜-2) g3(瓜-3) g4(瓜-4) g5(瓜-5) g6(瓜-6) g7(瓜-7) g8(瓜-8) 1-4 -- 是 --> 1-2 1-4 -- 否 --> 5-6 1-2 -- 是 --> 1 1-2 -- 否 --> 3 5-6 -- 是 --> 5 5-6 -- 否 --> 7 1 -- 是 --> g1 1 -- 否 --> g2 3 -- 是 --> g3 3 -- 否 --> g4 5 -- 是 --> g5 5 -- 否 --> g6 7 -- 是 --> g7 7 -- 否 --> g8

按照这个策略，我们只需要猜三次，就可以选中最好的西瓜。即我们只需要猜三次，就可以让不确定变成确定。

现在，我们把西瓜的数量改一下。
现在有16个西瓜，需要多少猜多少次？很简单，4次。
那么32个西瓜呢？5次。

被查找区间的大小变化：

n,n2,n4,88,⋯ ,n2k,⋯n,\frac{n}{2},\frac{n}{4},\frac{8}{8},\cdots,\frac{n}{2^k},\cdots

现在问，有n个西瓜，需要猜多少次？

O(log⁡n)O(\log n)

这就是二分法的时间复杂度，极其高效。

二分法的局限性

  1. 二分法依赖的数据结构是数组。
    链表不可以，因为二分法要频繁的根据下标去访问元素，而链表需要用一个一个的指针去指，时间复杂度是O(n)O(n)，有指过去的时间，不如直接遍历。
    但是，数组的话可以做到时间复杂度是O(1)O(1)。
  2. 二分法针对的是有序数据。
    因为每次选择一段都需要一个反馈，才能做下一步的二分操作。(买西瓜的例子，可以看成是按照特殊排序方法排序的有序数据)
  3. 数据量太大的话，不适合二分法。
    这个或许不太好理解，毕竟还有这么一个式子成立。lim⁡n→∞log⁡nn=0\lim_{n \rightarrow \infty} \frac{\log n}{n} = 0
    理论上应该数据量越大越适合二分法。但，二分法依赖于数组，数组要求是内存中的连续空间，如果我们的数据有1GB，那就要求1GB的连续的内存空间。所以数据量太大，不适合二分法。

二分法的应用

接下来我们来讨论二分法的5个常见应用。

  1. 查找是否存在等于给定值的元素
  2. 查找等于给定值的第一个位置
  3. 查找等于给定值的最后一个位置
  4. 查找大于等于给定值的第一个位置
  5. 查找小于等于给定值的最后一个位置

查找是否存在等于给定值的元素

  1. 如果中间值等于给定值，说明存在。
  2. 如果中间值大于给定值，说明在左边，rIndex左移。
  3. 如果中间值小于给定值，说明在右边，lIndex右移。

示例代码：

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
package ch06;

public class BinarySearchExist {

    /**
     * 二分法查找是否存在
     * @param sortedArr 排序之后的数组
     * @param num 需要查找的数
     * @return 是否存在
     */
    public static boolean binarySearchExist(int[] arr,int target){
        // 最左边数字的index
        int lIndex = 0;
        // 最右边数字的index
        int rIndex = arr.length - 1;
        // 中间数字的index
        int midIndex = 0;
        // 一定是 lIndex < rIndex
        // 不能是 lIndex != rIndex
        while (lIndex < rIndex){
            // 中间的index
            // 不写作 (lIndex + rIndex)/2 的原因是这样不容易溢出
            midIndex = lIndex + (rIndex - lIndex) / 2;
            if (arr[midIndex] == target){
                // 如果中间的数字就是要找的数字
                return true;
            }else if (arr[midIndex] > target){
                // 如果中间的数字比要找的数字大，说明在左侧。
                rIndex = midIndex - 1;
            }else{
                // 反之，如果中间的数字比要找的数字小，说明在右侧
                lIndex = midIndex + 1;
            }
        }
        return (arr[lIndex] == target);
    }
}

示例代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
def binarySearchExist(arr, target):
    # 最左边数字的index
    lIndex = 0
    # 最右边数字的index
    rIndex = len(arr) - 1
    # 中间数字的index
    midIndex = 0
    # 一定是 lIndex < rIndex
    # 不能是 lIndex != rIndex
    while lIndex < rIndex:
        # 中间的index
        # 不写作 (lIndex + rIndex) // 2 的原因是这样不容易溢出
        midIndex = lIndex + (rIndex - lIndex) // 2
        if arr[midIndex] == target:
            # 如果中间的数字就是要找的数字
            return True
        elif arr[midIndex] > target:
            # 如果中间的数字比要找的数字大，说明在左侧。
            rIndex = midIndex - 1
        else:
            # 反之，如果中间的数字比要找的数字小，说明在右侧
            lIndex = midIndex + 1

    return arr[lIndex] == target

查找等于给定值的第一个位置

第二个问题，我们加大难度了。等于给定值的第一个位置。
如果等于给定值的话，为了找第一个位置，我们还需要rIndex再左移，但是有可能左移就移出去了，所以我们再每一次相等的时候，并在左移之前，都把当前位置记下来。如果真移出去了，那么当前位置就是等于给定值的第一个位置。

示例代码：

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
package ch06;

public class BinarySearchFirstE {

    /**
     * 二分法查找是否存在
     * @param sortedArr 排序之后的数组
     * @param num 需要查找的数
     * @return 是否存在
     */
    public static int binarySearchFirstE(int[] arr,int target){
        // 记录位置
        int index = -1;
        // 最左边数字的index
        int lIndex = 0;
        // 最右边数字的index
        int rIndex = arr.length - 1;
        // 中间数字的index
        int midIndex = 0;
        while (lIndex <= rIndex){
            // 中间的index
            // 不写作 (lIndex + rIndex)/2 的原因是这样不容易溢出
            midIndex = lIndex + (rIndex - lIndex) / 2;
            if (arr[midIndex] == target){
                index = midIndex;
                rIndex = midIndex-1;
            }else if (arr[midIndex] > target){
                // 如果中间的数字比要找的数字大，说明在左侧。
                rIndex = midIndex - 1;
            }else{
                // 反之，如果中间的数字比要找的数字小，说明在右侧
                lIndex = midIndex + 1;
            }
        }
        return index;
    }
}

示例代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
def binarySearchFirstE(arr, target):
    # 记录位置
    index = -1
    # 最左边数字的index
    lIndex = 0
    # 最右边数字的index
    rIndex = len(arr) - 1
    # 中间数字的index
    midIndex = 0
    while lIndex <= rIndex:
        # 中间的index
        # 不写作 (lIndex + rIndex)/2 的原因是这样不容易溢出
        midIndex = lIndex + (rIndex - lIndex) // 2
        if arr[midIndex] == target:
            index = midIndex
            rIndex = midIndex - 1
        elif arr[midIndex] > target:
            # 如果中间的数字比要找的数字大，说明在左侧。
            rIndex = midIndex - 1
        else:
            # 反之，如果中间的数字比要找的数字小，说明在右侧
            lIndex = midIndex + 1

    return index

查找等于给定值的最后一个位置

这个问题和查找等于给定值的第一个位置差不多。
如果等于给定值的话，为了找第一个位置，我们需要lIndex右移。

示例代码：

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
package ch06;

public class BinarySearchLastE {

    public static int binarySearchLastE(int[] arr,int target){
        // 记录第一个位置
        int index = -1;
        // 最左边数字的index
        int lIndex = 0;
        // 最右边数字的index
        int rIndex = arr.length - 1;
        // 中间数字的index
        int midIndex = 0;
        // 一定是 lIndex < rIndex
        // 不能是 lIndex != rIndex
        while (lIndex <= rIndex){
            // 中间的index
            // 不写作 (lIndex + rIndex)/2 的原因是这样不容易溢出
            midIndex = lIndex + (rIndex - lIndex) / 2;
            if (arr[midIndex] == target){
                index = midIndex;
                lIndex = midIndex + 1;
            }else if (arr[midIndex] > target){
                // 如果中间的数字比要找的数字大，说明在左侧。
                rIndex = midIndex - 1;
            }else{
                // 反之，如果中间的数字比要找的数字小，说明在右侧
                lIndex = midIndex + 1;
            }
        }
        return index;
    }
}

示例代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
def binarySearchLastE(arr, target):
    # 记录位置
    index = -1
    # 最左边数字的index
    lIndex = 0
    # 最右边数字的index
    rIndex = len(arr) - 1
    # 中间数字的index
    midIndex = 0
    while lIndex <= rIndex:
        # 中间的index
        # 不写作 (lIndex + rIndex)/2 的原因是这样不容易溢出
        midIndex = lIndex + (rIndex - lIndex) // 2
        if arr[midIndex] == target:
            index = midIndex
            lIndex = midIndex + 1
        elif arr[midIndex] > target:
            # 如果中间的数字比要找的数字大，说明在左侧。
            rIndex = midIndex - 1
        else:
            # 反之，如果中间的数字比要找的数字小，说明在右侧
            lIndex = midIndex + 1

    return index

查找大于等于给定值的第一个位置

这个问题和查找等于给定值的第一个位置差不多。
大于等于给定值的情况下，我们都让rIndex左移。

示例代码：

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
package ch06;

public class BinarySearchFirstGE {

    /**
     * 二分法查找是否存在
     * @param sortedArr 排序之后的数组
     * @param num 需要查找的数
     * @return 是否存在
     */
    public static int binarySearchFirstGE(int[] arr,int target){
        int index = -1;
        // 最左边数字的index
        int lIndex = 0;
        // 最右边数字的index
        int rIndex = arr.length - 1;
        // 中间数字的index
        int midIndex = 0;
        // 一定是 lIndex <= rIndex
        while (lIndex <= rIndex){
            // 中间的index
            // 不写作 (lIndex + rIndex)/2 的原因是这样不容易溢出
            midIndex = lIndex + (rIndex - lIndex) / 2;
            if (arr[midIndex] >= target){
                index = midIndex;
                rIndex = midIndex - 1;
            }else{
                // 反之，如果中间的数字比要找的数字小，说明在右侧
                lIndex = midIndex + 1;
            }
        }
        return index;
    }
}

示例代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def binarySearchFirstGE(arr, target):
    # 记录位置
    index = -1
    # 最左边数字的index
    lIndex = 0
    # 最右边数字的index
    rIndex = len(arr) - 1
    # 中间数字的index
    midIndex = 0
    while lIndex <= rIndex:
        # 中间的index
        # 不写作 (lIndex + rIndex)/2 的原因是这样不容易溢出
        midIndex = lIndex + (rIndex - lIndex) // 2
        if arr[midIndex] >= target:
            index = midIndex
            rIndex = midIndex - 1
        else:
            # 反之，如果中间的数字比要找的数字小，说明在右侧
            lIndex = midIndex + 1

    return index

查找小于等于给定值的最后一个位置

这个问题和查找等于给定值的最后一个位置差不多。
大于等于给定值的情况下，我们都让lIndex右移。

示例代码：

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
package ch06;

public class BinarySearchLastLE {

    public static int binarySearchLastLE(int[] arr,int target){
        int index = -1;
        // 最左边数字的index
        int lIndex = 0;
        // 最右边数字的index
        int rIndex = arr.length - 1;
        // 中间数字的index
        int midIndex = 0;
        // 一定是 lIndex <= rIndex
        while (lIndex <= rIndex){
            // 中间的index
            // 不写作 (lIndex + rIndex)/2 的原因是这样不容易溢出
            midIndex = lIndex + (rIndex - lIndex) / 2;
            if (arr[midIndex] <= target){
                index = midIndex;
                lIndex = midIndex + 1;
            }else{
                // 反之，如果中间的数字比要找的数字小，说明在右侧
                rIndex = midIndex - 1;
            }
        }
        return index;
    }
}

示例代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def binarySearchLastLE(arr, target):
    # 记录位置
    index = -1
    # 最左边数字的index
    lIndex = 0
    # 最右边数字的index
    rIndex = len(arr) - 1
    # 中间数字的index
    midIndex = 0
    while lIndex <= rIndex:
        # 中间的index
        # 不写作 (lIndex + rIndex)/2 的原因是这样不容易溢出
        midIndex = lIndex + (rIndex - lIndex) // 2
        if arr[midIndex] <= target:
            index = midIndex
            lIndex = midIndex + 1
        elif arr[midIndex] > target:
            # 如果中间的数字比要找的数字大，说明在左侧。
            rIndex = midIndex - 1

    return index

对数器

示例代码：

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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
package ch06;

import java.util.ArrayList;
import java.util.Arrays;

/**
 * 对数器
 */
public class Comparator_BinarySearch {

    public static void main(String[] args) throws Exception {
        int testTimes = 500000;
        int maxSize = 100;
        int maxValue = 100;
        boolean isSuccess = true;
        for (int i = 0; i < testTimes; i++) {
            int[] arr = genRandomArr(maxSize,maxValue);
            if (null == arr || arr.length < 1){
                continue;
            }
            Arrays.sort(arr);
            int target = (int)(Math.random() * maxValue);

            ArrayList<Integer> aList = new ArrayList<Integer>();
            boolean a = searchExist(arr,target);
            aList.add(a?1:0);
            aList.add(searchFirstE(arr,target));
            aList.add(searchLastE(arr,target));
            aList.add(searchFirstGE(arr,target));
            aList.add(searchLastLE(arr,target));

            ArrayList<Integer> bList = new ArrayList<Integer>();
            boolean b = BinarySearchExist.binarySearchExist(arr,target);
            bList.add(b?1:0);
            bList.add(BinarySearchFirstE.binarySearchFirstE(arr,target));
            bList.add(BinarySearchLastE.binarySearchLastE(arr,target));
            bList.add(BinarySearchFirstGE.binarySearchFirstGE(arr,target));
            bList.add(BinarySearchLastLE.binarySearchLastLE(arr,target));

            if(!isEqual(aList,bList)){
                System.out.println(Arrays.toString(arr));
                System.out.println(target);
                System.out.println(aList);
                System.out.println(bList);
                isSuccess = false;
                break;
            }
        }
        System.out.print(isSuccess);
    }

    public static boolean isEqual(ArrayList<Integer> a,ArrayList<Integer> b){
        for (int i = 0; i < a.size(); i++) {
            if (a.get(i) != b.get(i)){
                return false;
            }
        }
        return true;
    }

    /**
     * 生成随机长度的随机无序数组
     * @param maxSize 数组的最大长度
     * @param maxValue 数组的最大值
     * @return 随机长度的随机无序数组
     */
    public static int[] genRandomArr(int maxSize,int maxValue){
        int[] arr = new int[(int)(Math.random() * maxSize)];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = (int)(Math.random() * maxValue);
        }
        return arr;
    }

    public static boolean searchExist(int[] arr,int target){
        boolean isExist = false;
        for (int i = 0; i < arr.length; i++) {
            if (arr[i]  == target){
                isExist = true;
                break;
            }
        }
        return isExist;
    }

    public static int searchFirstE(int[] arr,int target){
        int index = -1;
        for (int i = 0; i < arr.length; i++) {
            if (arr[i]  == target){
                index = i;
                break;
            }
        }
        return index;
    }

    public static int searchLastE(int[] arr,int target){
        int index = -1;
        boolean getEqual = false;
        for (int i = 0; i < arr.length; i++) {
            if (arr[i]  == target){
                getEqual = true;
            }
            if (getEqual == true){
                if (i == arr.length - 1){
                    index = i;
                    break;
                }else{
                    if (arr[i + 1] > target){
                        index = i;
                        break;
                    }
                }
            }
        }
        return index;
    }

    public static int searchFirstGE(int[] arr,int target){
        int index = -1;
        for (int i = 0; i < arr.length; i++) {
            if (arr[i]  >= target){
                index = i;
                break;
            }
        }
        return index;
    }

    public static int searchLastLE(int[] arr,int target){
        int index = -1;
        for (int i = 0; i < arr.length; i++) {
            if (arr[i]  > target){
                index = i-1;
                break;
            }
            if (i == arr.length - 1){
                index = i;
            }
        }
        return index;
    }

}
运行结果： 
1
true

示例代码：

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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
import random

from ch06 import BinarySearchExist, BinarySearchFirstE, BinarySearchLastE, BinarySearchFirstGE, BinarySearchLastLE


def gen_random_arr(max_size, max_value):
    """
    生成一个随机的数组
    :param max_size: 生成的随机数组的最大长度
    :param max_value: 生成的随机数组的最大值
    :return: 生成的随机数组
    """
    arr_rnt = []
    random_size = random.randint(0, max_size)
    for i in range(random_size):
        arr_rnt.append(random.randint(0, max_value))

    return arr_rnt


def search_exist(arr, target):
    is_exist = False
    for iter in arr:
        if iter == target:
            is_exist = True
            break

    return is_exist


def search_first_e(arr, target):
    index = -1
    for i in range(len(arr)):
        if arr[i] == target:
            index = i
            break

    return index


def search_last_e(arr, target):
    index = -1
    get_equal = False
    for i in range(len(arr)):
        if arr[i] == target:
            get_equal = True

        if get_equal:
            if i == (len(arr) - 1):
                index = i
                break
            elif arr[i + 1] > target:
                index = i
                break
    return index


def search_first_ge(arr, target):
    index = -1
    for i in range(len(arr)):
        if arr[i] >= target:
            index = i
            break

    return index


def search_last_le(arr, target):
    index = -1
    for i in range(len(arr)):
        if arr[i] > target:
            index = i - 1
            break
        if i == (len(arr) - 1):
            index = i

    return index


if __name__ == '__main__':
    testTimes = 500000
    maxSize = 100
    maxValue = 100
    is_success = True
    for i in range(testTimes):
        arr = gen_random_arr(maxSize, maxValue)

        if arr is None or len(arr) < 1:
            continue

        arr.sort()
        target = random.randint(0, maxValue)

        aList = []
        a = search_exist(arr, target)
        aList.append(1 if a else 0)
        aList.append(search_first_e(arr, target))
        aList.append(search_last_e(arr, target))
        aList.append(search_first_ge(arr, target))
        aList.append(search_last_le(arr, target))

        bList = []
        b = BinarySearchExist.binarySearchExist(arr, target)
        bList.append(1 if b else 0)
        bList.append(BinarySearchFirstE.binarySearchFirstE(arr, target))
        bList.append(BinarySearchLastE.binarySearchLastE(arr, target))
        bList.append(BinarySearchFirstGE.binarySearchFirstGE(arr, target))
        bList.append(BinarySearchLastLE.binarySearchLastLE(arr, target))

        if aList != bList:
            print(arr)
            print(target)
            print(aList)
            print(bList)
            is_success = False
            break

    print(is_success)
运行结果： 
1
True

二分插入排序

最后再回到二分插入排序。应该插入到哪个位置？
小于等于给定值的最后一个位置的再下一个位置。

示例代码：

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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
package ch06;

import java.util.Arrays;

/**
 * 插入排序
 */
public class BinaryInsertionSort {

    public static void main(String[] args) {
        int[] arr = {3,44,38,5,47,15,36,26,27,2,46,4,19,50,48};
        System.out.println(Arrays.toString(arr));
        // 只有数组不为空，并且数组的长度大于1，这时候的排序才有意义
        if (null != arr && arr.length > 1){
            arr = binaryInsertionSort(arr);
        }
        System.out.println(Arrays.toString(arr));
    }

    /**
     * 插入排序
     * @param arr
     * @return
     */
    public static int[] binaryInsertionSort(int[] arr){
        // i从1开始，先做到前2个数有序。
        // 为什么不是先做到前1个数有序？一个数字，不用排序了。
        for (int i = 1; i < arr.length; i++) {
            // 保存当前值
            int key = arr[i];
            // 利用二分查找定位插入位置
			int index = binarySearchLastLE(arr, key, 0, i - 1) + 1;
            // 将目标插入位置，同一时候右移目标位置右边的元素
            for (int j = i; j > index; j--) {
                arr[j] = arr[j - 1];
            }
            arr[index] = key;
        }

        return arr;
    }

    /**
     * 二分查找最后一个小于等于的位置
     * @param sortedArr
     * @param num
     * @param from
     * @param to
     * @return
     */
    private static int binarySearchLastLE(int[] sortedArr, int num, int from, int to) {
        int index = -1;
        // 最左边数字的index
        int lIndex = from;
        // 最右边数字的index
        int rIndex = to;
        // 中间数字的index
        int midIndex = 0;
        // 一定是 lIndex <= rIndex
        while (lIndex <= rIndex){
            // 中间的index
            // 不写作 (lIndex + rIndex)/2 的原因是这样不容易溢出
            midIndex = lIndex + (rIndex - lIndex) / 2;
            if (sortedArr[midIndex] <= num){
                index = midIndex;
                lIndex = midIndex + 1;
            }else{
                // 反之，如果中间的数字比要找的数字小，说明在右侧
                rIndex = midIndex - 1;
            }
        }
        return index;
    }

    /**
     * 互换
     * @param arr 数组
     * @param i 需要互换的元素的index
     * @param j 需要互换的元素的index
     */
    public static void swap(int[] arr,int i,int j){
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

}
运行结果： 
1
2
[3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48]
[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]

示例代码：

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
def binaryInsertionSort(arr_args):
    """
    二分插入排序
    :param arr_args: 需要排序的数组
    :return: 排序之后的数组
    """
    # i从1开始，先做到前2个数有序。
    # 为什么不是先做到前1个数有序？一个数字，不用排序了。
    for i in range(len(arr_args)):
        # 保存当前值
        key = arr_args[i]
        # 利用二分查找定位插入位置
        index = binarySearchLastLE(arr_args, key, 0, i - 1) + 1;
        # 将目标插入位置，同一时候右移目标位置右边的元素
        for j in range(i, index, -1):
            arr_args[j] = arr_args[j - 1]
        arr_args[index] = key

    return arr_args


def binarySearchLastLE(sortedArr, num, fromIndex, toIndex):
    # 记录位置
    index = -1
    # 最左边数字的index
    lIndex = fromIndex
    # 最右边数字的index
    rIndex = toIndex
    while lIndex <= rIndex:
        # 中间的index
        # 不写作 (lIndex + rIndex)/2 的原因是这样不容易溢出
        midIndex = lIndex + (rIndex - lIndex) // 2
        if sortedArr[midIndex] <= num:
            index = midIndex
            lIndex = midIndex + 1
        elif sortedArr[midIndex] > num:
            # 如果中间的数字比要找的数字大，说明在左侧。
            rIndex = midIndex - 1

    return index


if __name__ == '__main__':
    arr = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48]
    print(arr)
    print(binaryInsertionSort(arr))
运行结果： 
1
2
[3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48]
[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]
文章作者: Kaka Wan Yifan
文章链接: https://kakawanyifan.com/10606
版权声明: 本博客所有文章版权为文章作者所有，未经书面许可，任何机构和个人不得以任何形式转载、摘编或复制。
留言板