实现二分法查找
二分法查找，需要数组内是一个有序的序列
二分查找比线性查找：数组的元素数越多，效率提高的越明显
二分查找的效率表示：O(log2N) N在2的M次幂范围，那查找的次数最大就是M, log2N表示2的M次幂等于N, 省略常数，简写成O(logN)
如有一个200个元素的有序数组，那么二分查找的最大次数：
2^7=128, 2^8=256, 可以看出7次幂达不到200，8次幂包括， 所以最大查找次数就等于8
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
//循环，二分查找static int binarySearch(int[] array, int data) { int start = 0; int end = array.length - 1; int mid = -1; while (start <= end) { System.out.println("查找次数"); mid = (start + end) >>> 1; if (array[mid] < data) { start = mid + 1; } else if (array[mid] > data) { end = mid - 1; } else { return mid; } System.out.println("start=" + start+",end="+end+",mid="+mid); } return -1; } |
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
//递归二分查找 初始start=0, end = array.length - 1 static int binarySearch4Recursion(int[] array, int data, int start, int end) { int mid = -1; System.out.println("查找次数"); if (start > end) { return mid; } mid = (start + end) >>> 1; if (array[mid] < data) { return binarySearch4Recursion(array, data, mid + 1, end); } else if (array[mid] > data) { return binarySearch4Recursion(array, data, start, mid - 1); } else { return mid; } } |
二分法插入排序
设有一个序列a[0],a[1]...a[n];其中a[i-1]前是已经有序的,当插入时a[i]时,利用二分法搜索a[i]插入的位置
效率：O(N^2)，对于初始基本有序的序列，效率上不如直接插入排序；对于随机无序的序列，效率比直接插入排序要高
|
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
|
/* * 二分(折半)插入排序 * 设有一个序列a[0],a[1]...a[n];其中a[i-1]前是已经有序的,当插入时a[i]时,利用二分法搜索a[i]插入的位置 */ public class BinaryInsertSort { public static void main(String[] args) { int len = 10; int[] ary = new int[len]; Random random = new Random(); for (int j = 0; j < len; j++) { ary[j] = random.nextInt(1000); } binaryInsert(ary); /* * 复杂度分析： 最佳情况，即都已经排好序，则无需右移，此时时间复杂度为：O(n lg n) 最差情况，全部逆序，此时复杂度为O(n^2) * 无法将最差情况的复杂度提升到O(n|logn)。 */ // 打印数组 printArray(ary); } /** * 插入排序 * @param ary */ private static void binaryInsert(int[] ary) { int setValueCount = 0; // 从数组第二个元素开始排序，因为第一个元素本身肯定是已经排好序的 for (int j = 1; j < ary.length; j++) {// 复杂度 n // 保存当前值 int key = ary[j]; // ∆ 利用二分查找定位插入位置 // int index = binarySearchAsc(ary, ary[j], 0, j - 1);// 复杂度：O(logn) // int index = binarySearchDesc(ary, ary[j], 0, j - 1);// 复杂度：O(logn) int index = binarySearchDesc2(ary, ary[j], 0, j - 1);// 复杂度：O(logn) printArray(ary); System.out.println("第" + j +"个索引上的元素要插入的位置是：" + index); // 将目标插入位置，同时右移目标位置右边的元素 for (int i = j; i > index; i--) {// 复杂度,最差情况：(n-1)+(n-2)+...+n/2=O(n^2) ary[i] = ary[i - 1]; //i-1 <==> index setValueCount++; } ary[index] = key; setValueCount++; } System.out.println("\n 设值次数(setValueCount)=====> " + setValueCount); } /** * 二分查找 升序 递归 * * @param ary * 给定已排序的待查数组 * @param target * 查找目标 * @param from * 当前查找的范围起点 * @param to * 当前查找的返回终点 * @return 返回目标在数组中，按顺序应在的位置 */ private static int binarySearchAsc(int[] ary, int target, int from, int to) { int range = to - from; // 如果范围大于0，即存在两个以上的元素，则继续拆分 if (range > 0) { // 选定中间位 int mid = (to + from) / 2; // 如果临界位不满足，则继续二分查找 if (ary[mid] > target) { /* * mid > target, 升序规则，target较小，应交换位置 前置， 即target定位在mid位置上， * 根据 查找思想， 从from到 mid-1认为有序， 所以to=mid-1 */ return binarySearchAsc(ary, target, from, mid - 1); } else { /* * mid < target, 升序规则，target较大，不交换位置，查找比较的起始位置应为mid+1 */ return binarySearchAsc(ary, target, mid + 1, to); } } else { if (ary[from] > target) {//如 5,4, 要插入的是4 return from; } else { return from + 1; } } } /** * 二分查找 降序， 递归 */ private static int binarySearchDesc(int[] ary, int target, int from, int to) { int range = to - from; if (range > 0) { int mid = (from + to) >>> 1; if (ary[mid] > target) { return binarySearchDesc(ary, target, mid + 1, to); } else { return binarySearchDesc(ary, target, from, mid - 1); } } else { if (ary[from] > target) {//如 5,4, 要插入的是4 return from + 1; } else { return from; } } } /** * 二分查找 降序， 非递归 */ private static int binarySearchDesc2(int[] ary, int target, int from, int to) { // while(from < to) { for (; from < to; ) { int mid = (from + to) >>> 1; if (ary[mid] > target) { from = mid + 1; } else { to = mid -1; } } //from <==> to; if (ary[from] > target) {//如 5,4, 要插入的是4 return from + 1; } else { return from; } } private static void printArray(int[] ary) { for (int i : ary) { System.out.print(i + " "); } } } |
打印
|
1
2
3
4
5
6
7
8
9
|
918 562 442 531 210 216 931 706 333 132 第1个索引上的元素要插入的位置是：1 918 562 442 531 210 216 931 706 333 132 第2个索引上的元素要插入的位置是：2 918 562 442 531 210 216 931 706 333 132 第3个索引上的元素要插入的位置是：2 918 562 531 442 210 216 931 706 333 132 第4个索引上的元素要插入的位置是：4 918 562 531 442 210 216 931 706 333 132 第5个索引上的元素要插入的位置是：4 918 562 531 442 216 210 931 706 333 132 第6个索引上的元素要插入的位置是：0 931 918 562 531 442 216 210 706 333 132 第7个索引上的元素要插入的位置是：2 931 918 706 562 531 442 216 210 333 132 第8个索引上的元素要插入的位置是：6 931 918 706 562 531 442 333 216 210 132 第9个索引上的元素要插入的位置是：9 |
设值次数(setValueCount)=====> 24
|
1
|
931 918 706 562 531 442 333 216 210 132 |
