ShiYu

# 第1节 认识复杂度、对数器、二分法

# 评估算法优劣的核心指标是什么？

时间复杂度（流程决定）

额外空间复杂度（流程决定）

常数项时间（实现细节决定）

# 时间复杂度

# 什么是时间复杂度？时间复杂度怎么估算？

  • 常数时间的操作

    • 何为常数时间的操作?

      如果一个操作的执行时间不以具体样本量为转移，每次执行时间都是固定时间。称这样的操作为常数时间的操作。

    • 常见的常数时间的操作

      • 常见的算术运算（+、-、*、/、% 等）
      • 常见的位运算（>>、>>>、<<、|、&、^等）
      • 赋值、比较、自增、自减操作等
      • 数组寻址操作

      总之，执行时间固定的操作都是常数时间的操作。 反之，执行时间不固定的操作，都不是常数时间的操作。

  • 确定算法流程的总操作数量与样本数量之间的表达式关系

    • 如何确定算法流程的总操作数量与样本数量之间的表达式关系？

      1. 想象该算法流程所处理的数据状况，要按照最差情况来。
      2. 把整个流程彻底拆分为一个个基本动作，保证每个动作都是常数时间的操作。
      3. 如果数据量为N，看看基本动作的数量和N是什么关系。

  • 只看表达式最高阶项的部分

    • 如何确定算法流程的时间复杂度？

      当完成了表达式的建立，只要把最高阶项留下即可。低阶项都去掉，高阶项的系数也去掉。 记为：O(忽略掉系数的高阶项)

# 通过三个具体的例子，来实践一把时间复杂度的估算

# 选择排序

过程： arr[0～N-1]范围上，找到最小值所在的位置，然后把最小值交换到0位置。 arr[1～N-1]范围上，找到最小值所在的位置，然后把最小值交换到1位置。 arr[2～N-1]范围上，找到最小值所在的位置，然后把最小值交换到2位置。 … arr[N-1～N-1]范围上，找到最小值位置，然后把最小值交换到N-1位置。

估算： 很明显，如果arr长度为N，每一步常数操作的数量，如等差数列一般 所以，总的常数操作数量 = a*(N^2) + b*N + c (a、b、c都是常数) 时间复杂度:O(N^2)

示例：

package class01;

import java.util.Arrays;

/**
 * 	测试选择排序
 * @author yangyanchao
 *
 */
public class Test01_SelectionSort {
	
	
	/**
	 * 	选择排序
	 * 	arr[0～N-1]范围上，找到最小值所在的位置，然后把最小值交换到0位置。
	 * 	arr[1～N-1]范围上，找到最小值所在的位置，然后把最小值交换到1位置。
	 * 	arr[2～N-1]范围上，找到最小值所在的位置，然后把最小值交换到2位置。
	 * 	…
	 * 	arr[N-1～N-1]范围上，找到最小值位置，然后把最小值交换到N-1位置。
	 * @param arr
	 */
	public static void selectionSort(int[] arr) {
		if(arr == null || arr.length < 2) {
			return;
		}
		for(int i = 0; i < arr.length - 1; i++) {
			int minIndex = i;
			for(int j = i + 1; j < arr.length; j++) {
				minIndex = arr[minIndex] < arr[j] ? minIndex : j;
			}
			swap(arr, i, minIndex);
		}
	}
	
	/**
	 * 	交换
	 * @param arr
	 * @param i
	 * @param j
	 */
	private static void swap(int[] arr, int i, int j) {
		int temp = arr[i];
		arr[i] = arr[j];
		arr[j] = temp;
	}

	public static void main(String[] args) {
		int testTimes = 500000;
		int maxSize = 100;
		int maxValue = 100;
		boolean succeed = true;
		for (int i = 0; i < testTimes; i++) {
			int[] arr1 = generateRandomArray(maxSize, maxValue);
			int[] arr2 = copyArray(arr1);
			selectionSort(arr1);
			comparator(arr2);
			if(!isEqual(arr1, arr2)) {
				succeed = false;
				printArray(arr1);
				printArray(arr2);
				break;
			}
		}
		System.out.println(succeed ? "Nice." : "Fucking fucked!");
	}

	/**
	 * 	打印数组
	 * @param arr1
	 */
	private static void printArray(int[] arr1) {
		if(arr1 == null || arr1.length == 0) {
			return;			
		}
		System.out.print("{ ");
		for (int i = 0; i < arr1.length; i++) {
			System.out.print(arr1[i]+ " ");
		}
		System.out.println("}");
	}

	/**
	 * 	校验函数
	 * @param arr1
	 * @param arr2
	 * @return
	 */
	private static boolean isEqual(int[] arr1, int[] arr2) {
		if(arr1 == null || arr2 == null || arr1.length != arr2.length) {
			return false;			
		}
		boolean flag = true;
		for (int i = 0; i < arr1.length; i++) {
			if(arr2[i] != arr1[i]) {
				return false;
			}
		}
		return flag;
	}

	/**
	 * 	比较函数
	 * @param arr2
	 */
	private static void comparator(int[] arr) {
		Arrays.sort(arr);
	}

	/**
	 * 	复制数组
	 * @param arr1
	 * @return
	 */
	private static int[] copyArray(int[] arr1) {
		if (arr1 == null) {
			return null;
		}
		int[] arr2 = new int[arr1.length];
		for (int i = 0; i < arr1.length; i++) {
			arr2[i] = arr1[i];
		}
		return arr2;
	}

	/**
	 *	随机生成size和value的数组函数
	 * @param maxSize
	 * @param maxValue
	 * @return
	 */
	private static int[] generateRandomArray(int maxSize, int maxValue) {
		int[] arr = new int[(int)((maxSize + 1) * Math.random())];
		for (int i = 0; i< arr.length; i++) {
			arr[i] = (int)(((maxValue + 1) * Math.random()) - ((maxValue + 1) * Math.random()));
		}
		return arr;
	}
}
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

# 冒泡排序

过程： 在arr[0～N-1]范围上： arr[0]和arr[1]，谁大谁来到1位置；arr[1]和arr[2]，谁大谁来到2位置…arr[N-2]和arr[N-1]，谁大谁来到N-1位置

在arr[0～N-2]范围上，重复上面的过程，但最后一步是arr[N-3]和arr[N-2]，谁大谁来到N-2位置 在arr[0～N-3]范围上，重复上面的过程，但最后一步是arr[N-4]和arr[N-3]，谁大谁来到N-3位置 … 最后在arr[0～1]范围上，重复上面的过程，但最后一步是arr[0]和arr[1]，谁大谁来到1位置

估算： 很明显，如果arr长度为N，每一步常数操作的数量，依然如等差数列一般 所以，总的常数操作数量 = a*(N^2) + b*N + c(a、b、c都是常数)

时间复杂度:O(N^2)

示例：

package class01;

import java.util.Arrays;

/**
 * 	测试冒泡排序
 * 
 * @author yangyanchao
 *
 */
public class Test02_BubbleSort {

	/**
	 * 	冒泡排序 在arr[0～N-1]范围上：
	 *	arr[0]和arr[1]，谁大谁来到1位置；arr[1]和arr[2]，谁大谁来到2位置…arr[N-2]和arr[N-1]，谁大谁来到N-1位置
	 * 	在arr[0～N-2]范围上，重复上面的过程，但最后一步是arr[N-3]和arr[N-2]，谁大谁来到N-2位置
	 * 	在arr[0～N-3]范围上，重复上面的过程，但最后一步是arr[N-4]和arr[N-3]，谁大谁来到N-3位置 …
	 * 	最后在arr[0～1]范围上，重复上面的过程，但最后一步是arr[0]和arr[1]，谁大谁来到1位置
	 * 
	 * @param arr
	 */
	public static void bubbleSort(int[] arr) {
		if (arr == null || arr.length < 2) {
			return;
		}
		for (int i = arr.length - 1; i > 0; i--) {
			for (int j = 0; j < i; j++) {
				if (arr[j] > arr[j + 1]) {
					swap(arr, j, j + 1);
				}
			}
		}
	}

	/**
	 * 	交换
	 * 
	 * @param arr
	 * @param j
	 * @param i
	 */
	private static void swap(int[] arr, int i, int j) {
		int temp = arr[i];
		arr[i] = arr[j];
		arr[j] = temp;
	}

	public static void main(String[] args) {
		int maxTimes = 500000;
		int maxSize = 100;
		int maxValue = 100;
		boolean successed = true;
		for (int i = 0; i < maxTimes; i++) {
			int[] arr1 = generateRandomArray(maxSize, maxValue);
			int[] arr2 = copyArray(arr1);
			bubbleSort(arr1);
			compare(arr2);
			if (!isEqual(arr1, arr2)) {
				successed = false;
				printArray(arr1);
				printArray(arr2);
				break;
			}
		}
		System.out.println(successed ? "Nice." : "oo^oo");

	}

	private static void compare(int[] arr2) {
		Arrays.sort(arr2);
	}

	/**
	 * 	打印数组
	 * @param arr1
	 */
	private static void printArray(int[] arr1) {
		if(arr1 == null || arr1.length == 0) {
			return ;		
		}
		System.out.print("{");
		for(int i = 0; i < arr1.length; i++) {
			System.out.print(arr1[i] + " ");
		}
		System.out.println("}");
	}

	/**
	 * 	判断俩个数组是否一致
	 * @param arr1
	 * @param arr2
	 * @return
	 */
	private static boolean isEqual(int[] arr1, int[] arr2) {
		if (arr1 == null || arr2 == null || arr1.length != arr2.length) {
			return false;
		}
		for(int i = 0; i < arr1.length; i++) {
			if (arr2[i] != arr1[i]) {
				return false;
			}
		}
		return true;
	}

	/**
	 * 	根据一个数组复制一个数组
	 * @param arr1
	 * @return
	 */
	private static int[] copyArray(int[] arr1) {
		if(arr1 == null) {
			return null;			
		}
		int[] arr2 = new int[arr1.length];
		for(int i = 0; i < arr1.length; i++) {
			arr2[i] = arr1[i];
		}
		return arr2;
	}

	/**
	 * 	生成随机长度及随机数值的数组
	 * 
	 * @param maxSize
	 * @param maxValue
	 * @return
	 */
	private static int[] generateRandomArray(int maxSize, int maxValue) {
		int[] arr = new int[(int) ((maxSize + 1) * Math.random())];
		for (int i = 0; i < arr.length; i++) {
			arr[i] = (int) (((maxValue + 1) * Math.random()) -  ((maxValue + 1) * Math.random()));
		}
		return arr;
	}
}
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

# 插入排序

过程： 想让arr[0~0]上有序，这个范围只有一个数，当然是有序的。 想让arr[0~1]上有序，所以从arr[1]开始往前看，如果arr[0]>arr[1]，就交换。否则什么也不做。 … 想让arr[0~i]上有序，所以从arr[i]开始往前看，arr[i]这个数不停向左移动，一直移动到左边的数字不再比自己大，停止移动。 最后一步，想让arr[0~N-1]上有序， arr[N-1]这个数不停向左移动，一直移动到左边的数字不再比自己大，停止移动。

估算：

估算时发现这个算法流程的复杂程度，会因为数据状况的不同而不同。

如果某个算法流程的复杂程度会根据数据状况的不同而不同，那么你必须要按照最差情况来估计。

很明显，在最差情况下，如果arr长度为N，插入排序的每一步常数操作的数量，还是如等差数列一般

所以，总的常数操作数量 = a*(N^2) + b*N + c (a、b、c都是常数)

时间复杂度:O(N^2)

示例：

package class01;

import java.util.Arrays;

/**
 * 	插入排序
 * 
 * @author yangyanchao
 *
 */
public class Test03_InsertionSort {

	/**
	 * 	插入排序 想让arr[0~0]上有序，这个范围只有一个数，当然是有序的。
	 * 	想让arr[0~1]上有序，所以从arr[1]开始往前看，如果arr[0]>arr[1]，就交换。否则什么也不做。 …
	 * 	想让arr[0~i]上有序，所以从arr[i]开始往前看，arr[i]这个数不停向左移动，一直移动到左边的数字不再比自己大，停止移动。
	 * 	最后一步，想让arr[0~N-1]上有序， arr[N-1]这个数不停向左移动，一直移动到左边的数字不再比自己大，停止移动。
	 * 
	 * @param arr
	 */
	public static void insertionSort(int[] arr) {
		if (arr == null || arr.length < 2) {
			return;
		}
		for (int i = 1; i < arr.length; i++) {
			for (int j = i - 1; j <= 0 && arr[j] > arr[j + 1]; j--) {
				swap(arr, j, j + 1);
			}
		}
	}

	/**
	 * 	交换
	 * 
	 * @param arr
	 * @param j
	 * @param i
	 */
	private static void swap(int[] arr, int i, int j) {
		int temp = arr[i];
		arr[i] = arr[j];
		arr[j] = temp;
	}

	public static void main(String[] args) {
		int maxTimes = 500000;
		int maxSize = 100;
		int maxValue = 100;
		boolean successed = true;
		for (int i = 0; i < maxTimes; i++) {
			int[] arr1 = generateRandomArray(maxSize, maxValue);
			int[] arr2 = copyArray(arr1);
			insertionSort(arr1);
			compare(arr2);
			if (!isEqual(arr1, arr2)) {
				successed = false;
				printArray(arr1);
				printArray(arr2);
				break;
			}
		}
		System.out.println(successed ? "Nice." : "oo^oo");
	}

	/**
	 * 	打印数组
	 * 
	 * @param arr1
	 */
	private static void printArray(int[] arr1) {
		if (arr1 == null) {
			return;
		}
		System.out.print("{");
		for (int i = 0; i < arr1.length; i++) {
			System.out.print(arr1[i] + " ");
		}
		System.out.println("}");
	}

	/**
	 * 判断arr1与arr2是否相等
	 * 
	 * @param arr1
	 * @param arr2
	 * @return
	 */
	private static boolean isEqual(int[] arr1, int[] arr2) {
		if (arr1 == null || arr2 == null || arr1.length != arr2.length) {
			return false;
		}
		for (int i = 0; i < arr1.length; i++) {
			if (arr1[i] != arr2[i]) {
				return false;
			}
		}
		return true;
	}

	/**
	 * 比较数组
	 * 
	 * @param arr2
	 */
	private static void compare(int[] arr2) {
		Arrays.sort(arr2);
	}

	/**
	 * 复制数组
	 * 
	 * @param arr1
	 * @return
	 */
	private static int[] copyArray(int[] arr1) {
		if (arr1 == null) {
			return null;
		}
		int[] arr2 = new int[arr1.length];
		for (int i = 0; i < arr1.length; i++) {
			arr2[i] = arr1[i];
		}
		return arr2;
	}

	/**
	 * 生成随机长度及数值的数组函数
	 * 
	 * @param maxSize
	 * @param maxValue
	 * @return
	 */
	private static int[] generateRandomArray(int maxSize, int maxValue) {
		int[] arr = new int[(int) ((maxSize + 1) * Math.random())];
		for (int i = 0; i < arr.length; i++) {
			arr[i] = (int) (((maxSize + 1) * Math.random()) - ((maxSize + 1) * Math.random()));
		}
		return arr;
	}
}
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

注意:

1，算法的过程，和具体的语言是无关的。

2，想分析一个算法流程的时间复杂度的前提，是对该流程非常熟悉

3，一定要确保在拆分算法流程时，拆分出来的所有行为都是常数时间的操作。这意味着你写算法时，对自己的用过的每一个系统api，都非常的熟悉。否则会影响你对时间复杂度的估算。

# 额外空间复杂度

你要实现一个算法流程，在实现算法流程的过程中，你需要开辟一些空间来支持你的算法流程。

作为输入参数的空间，不算额外空间。 作为输出结果的空间，也不算额外空间。

因为这些都是必要的、和现实目标有关的。所以都不算。

但除此之外，你的流程如果还需要开辟空间才能让你的流程继续下去。这部分空间就是额外空间。

如果你的流程只需要开辟有限几个变量，额外空间复杂度就是O(1)。

# 常数项时间

# 算法流程的常数项

我们会发现，时间复杂度这个指标，是忽略低阶项和所有常数系数的。

难道同样时间复杂度的流程，在实际运行时候就一样的好吗？

当然不是。

时间复杂度只是一个很重要的指标而已。如果两个时间复杂度一样的算法，你还要去在时间上拼优劣，就进入到拼常数时间的阶段，简称拼常数项。

# 算法流程的常数项的比拼方式

放弃理论分析，生成随机数据直接测。

为什么不去理论分析？

不是不能纯分析，而是没必要。因为不同常数时间的操作，虽然都是固定时间，但还是有快慢之分的。

比如，位运算的常数时间原小于算术运算的常数时间，这两个运算的常数时间又远小于数组寻址的时间。

所以如果纯理论分析，往往会需要非常多的分析过程。都已经到了具体细节的程度，莫不如交给实验数据好了。

# 面试、比赛、刷题中，一个问题的最优解是什么意思？

一般情况下，认为解决一个问题的算法流程，在时间复杂度的指标上，一定要尽可能的低，先满足了时间复杂度最低这个指标之后，使用最少的空间的算法流程，叫这个问题的最优解。

一般说起最优解都是忽略掉常数项这个因素的，因为这个因素只决定了实现层次的优化和考虑，而和怎么解决整个问题的思想无关。

# 常见的时间复杂度(我们陆续都会见到的)

排名从好到差： O(1) O(logN) O(N) O(N*logN) O(N^2) O(N^3) … O(N^K) O(2^N) O(3^N) … O(K^N) O(N!)

# 算法和数据结构学习的大脉络

1）知道怎么算的算法

2）知道怎么试的算法 图灵是我们的祖师爷

我们所有的题目讲解，对于大脉络的实践贯穿始终

# 认识对数器

1，你想要测的方法a 2，实现复杂度不好但是容易实现的方法b 3，实现一个随机样本产生器 4，把方法a和方法b跑相同的随机样本，看看得到的结果是否一样 5，如果有一个随机样本使得比对结果不一致，打印样本进行人工干预，改对方法a和方法b 6，当样本数量很多时比对测试依然正确，可以确定方法a已经正确。

# 认识二分法

经常见到的类型是在一个有序数组上，开展二分搜索 但有序真的是所有问题求解时使用二分的必要条件吗？ 不 只要能正确构建左右两侧的淘汰逻辑，你就可以二分。

# 在一个有序数组中，找某个数是否存在

示例：先排序，再使用二分查找法

package class01;

import java.util.Arrays;

/**
 * 	二分查找法 O(LogN)
 * @author yangyanchao
 *
 */
public class Test04_BinarySearchExist {
	
	/**
	 * 	使用二分查找判断数组arr中是否存在searchVal
	 * @param arr
	 * @param searchVal
	 * @return
	 */
	public static boolean binarySearchExist1(int[] arr, int searchVal) {
		if (arr == null || arr.length == 0) {
			return false;
		}
		int L = 0;
		int R = arr.length - 1;
		while(L < R) {
			int middle = L + ((R - L) >> 1);
			if(arr[middle] == searchVal) {
				return true;
			} else if(arr[middle] > searchVal) {
				// 那么searchVal要往左边再去查找
				R = middle - 1;
			} else {
				// 那么searchVal要往右边再去查找
				L = middle + 1;
			}
		}
		return arr[L] == searchVal;
	}

	/**
	 * 	使用二分查找法判断searchVal是否存在
	 * @param arr
	 * @param searchVal
	 * @return
	 */
	public static boolean binarySearchExist(int[] arr, int searchVal) {
		if(arr == null || arr.length == 0) {
			return false;
		}
		int L = 0;
		int R = arr.length - 1;
		int M = 0;
		while(L < R) {
			M = L + ((R - L) >> 1);
			if(arr[M] == searchVal) {	
				return true;
			} else if(arr[M] > searchVal) {
				R = M - 1;
			} else {
				L = M + 1;
			}
		}
		return arr[L] == searchVal;
	}
	
	public static void main(String[] args) {
		int maxTimes = 500000;
		int maxSize = 5;
		int maxValue = 5;
		boolean succeed = true;
		for(int i = 0; i < maxTimes; i++) {
			int[] arr1 = generateRandomArray(maxSize, maxValue);
			Arrays.sort(arr1);
			int searchVal = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random());
			if(binarySearchExist(arr1, searchVal) != compareExist(arr1, searchVal)) {
				succeed = false;
				printArray(arr1);
				break;
			}
		}
		System.out.println(succeed ? "Nice." : "ooVoo");
		
	}

	/**
	 * 	打印数组
	 * @param arr1
	 */
	private static void printArray(int[] arr1) {
		if(arr1 == null || arr1.length == 0) {
			return ;
		}
		System.out.print("{");
		for(int i = 0; i<arr1.length;i++) {
			System.out.print(arr1[i]+" ");
		}
		System.out.println("}");
	}

	/**
	 * 	O(N)的普通查找方法
	 * @param arr2
	 * @param searchVal
	 * @return
	 */
	private static boolean compareExist(int[] arr1, int searchVal) {
		if(arr1 == null || arr1.length == 0) {
			return false;
		}
		for(int item : arr1) {
			if(item == searchVal) {
				return true;
			}
		}
		return false;
	}

	/**
	 * 	复制数组
	 * @param arr1
	 * @return
	 */
	private static int[] copyArray(int[] arr1) {
		if(arr1 == null) {
			return null;
		}
		int[] arr2 = new int[arr1.length];
		for(int i = 0; i < arr1.length; i++) {
			arr2[i] = arr1[i];
		}
		return arr2;
	}

	/**
	 * 	生成长度及值随机的数组
	 * @param maxSize
	 * @param maxValue
	 * @return
	 */
	private static int[] generateRandomArray(int maxSize, int maxValue) {
		int[] arr = new int[(int) ( (maxSize + 1) * Math.random())];
		for(int i =0; i<arr.length;i++) {
			arr[i] = (int) (((maxValue+1)*Math.random()) - ((maxValue+1)*Math.random()));
		}
		return arr;
	}
}
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
145
146
147

# 在一个有序数组中，找>=某个数最左侧的位置

示例：先排序，再使用二分查找法

package class01;

import java.util.Arrays;

/**
 * 	使用二分法 
 * 	在一个有序数组中，找>=某个数最左侧的位置
 * @author yangyanchao
 *
 */
public class Test05_BSNearLeft {
	/**
	 * 	在一个有序数组中，找>=某个数最左侧的位置
	 * 
	 * @param sortedArr
	 * @param num
	 * @return
	 */
	public static int bsNearLeft(int[] sortedArr, int num) {
		if(sortedArr == null || sortedArr.length == 0) {
			return -1;
		}
		int index = -1;// 记录最左的对号
		int L = 0;
		int R = sortedArr.length - 1;
		while (L <= R) {// 至少一个数的时候
			int middle = L + ((R - L) >> 1);
			if (sortedArr[middle] >= num) {
				// 还要往左侧找
				index = middle;
				R = middle - 1;
			} else {
				L = middle + 1;
			}
		}
		return index;
	}

	public static void main(String[] args) {
		int maxTimes = 500000;
		int maxSize = 100;
		int maxValue = 100;
		boolean succed = true;
		for (int i = 0; i < maxTimes; i++) {
			int[] arr = generateRandomArray(maxSize, maxValue);
			int testVal = (int) (((maxValue + 1) * Math.random()) - (maxValue * Math.random()));
			Arrays.sort(arr);
			if (bsNearLeft(arr, testVal) != compare(arr, testVal)) {
				succed = false;
				printArray(arr);
				break;
			}
		}
		System.out.println(succed ? "Nice." : "ooVoo");
	}

	/**
	 * 打印数组
	 * 
	 * @param arr
	 */
	private static void printArray(int[] arr) {
		if (arr == null || arr.length == 0) {
			return;
		}
		System.out.print("{ ");
		for (int i = 0; i < arr.length; i++) {
			System.out.print(arr[i] + " ");
		}
		System.out.println("}");
	}

	/**
	 * 比对函数
	 * 
	 * @param arr
	 * @param testVal
	 * @return
	 */
	private static int compare(int[] arr, int testVal) {
		for (int i = 0; i < arr.length; i++) {
			if (arr[i] >= testVal) {
				return i;
			}
		}
		return -1;
	}

	/**
	 * 生成长度及数值随机的数组
	 * 
	 * @param maxSize
	 * @param maxValue
	 * @return
	 */
	private static int[] generateRandomArray(int maxSize, int maxValue) {
		int[] arr = new int[(int) ((maxSize + 1) * Math.random())];
		for (int i = 0; i < arr.length; i++) {
			arr[i] = (int) (((maxValue + 1) * Math.random()) - (maxValue * Math.random()));
		}
		return arr;
	}
}
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

# 在一个有序数组中，找<=某个数最右侧的位置

示例：先排序，再使用二分查找法

package class01;

import java.util.Arrays;

/**
 * 	使用二分法
 * 	在一个有序数组中，找<=某个数最右侧的位置
 * @author yangyanchao
 *
 */
public class Test06_BSNearRight {
	/**
	 * 	在一个有序数组中，找<=某个数最右侧的位置
	 * @param sortedArr
	 * @param num
	 * @return
	 */
	public static int bsNearRight(int[] sortedArr, int num) {
		if(sortedArr == null || sortedArr.length == 0) {
			return -1;
		}
		int index = -1;// 记录最右侧的位置
		int L = 0;
		int R = sortedArr.length - 1;
		while(L <= R) {// 至少有一个值
			int middle = L + ((R - L) >> 1);
			if(sortedArr[middle] <= num) {
				index = middle;
				// 还要往右侧看
				L = middle + 1;
			} else {
				R = middle - 1;
			}
		}
		return index;
	}
	public static void main(String[] args) {
		int maxTimes = 500000;
		int maxSize = 100;
		int maxVal = 100;
		boolean succed = true;
		for(int i=0;i<maxTimes;i++) {
			int[] arr = generateRandomArray(maxSize, maxVal);
			Arrays.sort(arr);
			int num = (int)(((maxVal + 1) * Math.random()) - (maxVal * Math.random()));
			if(bsNearRight(arr, num) != compare(arr, num)) {
				printArray(arr);
				System.out.println(num);
				System.out.println(compare(arr, num));
				System.out.println(bsNearRight(arr, num));
				succed = false;
				break;
			}
		}
		System.out.println(succed ? "Nice." : "ooVoo");
	}
	/**
	 * 	打印数组
	 * @param arr
	 */
	private static void printArray(int[] arr) {
		System.out.print("{ ");
		for(int i = 0; i< arr.length; i++) {
			System.out.print(arr[i] + " ");
		}
		System.out.println("}");
	}
	/**
	 * 	比对函数
	 * @param arr
	 * @param num
	 * @return
	 */
	private static int compare(int[] arr, int num) {
		if(arr == null || arr.length == 0) {
			return -1;
		}
		for (int i = arr.length - 1; i >= 0; i--) {
			if (arr[i] <= num) {
				return i;
			}
		}
		return -1;
	}
	/**
	 * 	生成长度及数值随机的数组
	 * @param maxSize
	 * @param maxVal
	 * @return
	 */
	private static int[] generateRandomArray(int maxSize, int maxVal) {
		int[] arr = new int[(int)((maxSize + 1) * Math.random())];
		for(int i=0;i<arr.length;i++) {
			arr[i] = (int)(((maxVal + 1) * Math.random()) - (maxVal * Math.random()));
		}
		return arr;
	}
}
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

# 局部最小值问题

示例：不通过排序后的数组，也能使用二分查找法

局部最小值：某个数X与自己相邻的元素都小的值

边界：0位置和N-1位置上的

0位置上比1位置小，返回0

N-1位置上比N-2位置小，返回N-1

package class01;

/**
 * 	局部最小值
 * 	不通过排序后的数组，也能使用二分查找法
 * @author yangyanchao
 *
 */
public class Test07_BSAwesome {
	/**
	 * 	局部最小值：某个数X与自己相邻的元素都小的值`
	 * 	边界：
	 * 	0位置上比1位置小，返回0
	 * 	N-1位置上比N-2位置小，返回N-1
	 * @param arr
	 * @param num
	 * @return
	 */
	public static int bsAwesome(int[] arr) {
		if(arr == null || arr.length == 0) {
			return -1;
		}
		if(arr.length == 1 || arr[0] < arr[1]) {
			return 0;
		}
		if(arr[arr.length - 1] < arr[arr.length - 2]) {
			return arr.length - 1;
		}
		int middle = 0;
		int L = 1;
		int R = arr.length - 2;
		while(L < R) {
			middle = L + ((R - L) >> 1);
			if(arr[middle] > arr[middle - 1]) {
				// 0至1位置上是下降趋势，middle - 1至middle是上升趋势 
				// 说明arr数组1至middle - 1中间必定存在局部最小值
				R = middle - 1;
			} else if(arr[middle] > arr[middle + 1]) {
				// middle至middle + 1是下降趋势， N-2至N-1位置上是上升趋势 
				// 说明arr数组middle + 1至N-2中间必定存在局部最小值
				L = middle + 1;
			} else {
				return middle;
			}
		}
		return L;
		
	}
	public static void main(String[] args) {
		
	}
}
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

← 第2节 异或运算相关面试题 →