剑指offer面试题8 旋转数组的最小数字

考察点

算法二分搜索
1

知识点

二分搜索算法是针对排序的数组，先找到中间元素，如果待查找元素比中间元素大，说明待查
找元素肯定不在左边那片区域内，如果待查找元素比中间元素小，说明待查找元素肯定不在右
边那片区域内，反复进行该过程直到找到元素为止对于搜索而言，降低复杂度的唯一方式就是
每一次轮询以后能缩小搜索范围或者过滤掉更多的不可能元素，我们最普通的遍历数组的方式
，每轮询完一次只能过滤掉一个元素。而二分搜索每轮询完一次可以过滤掉一半的元素，因此
这就是它非常高效的原因(log(n))
1
2
3
4
5
6

题目

分析
首先一定要记住只要看到排序数组的查找，思维一定要往二分法上靠，然后再思考清楚如何利用二分法。而如何利用二分法一定要仔细分析所给的数组的特点：递增数组且最开始的若干元素搬到数组的末尾，相当于该数组由俩个递增小数组构成，前面的数组元素肯定大于等于后面的数组元素，且最小值肯定是第二个小数组的第一个元素。二分法需要首尾俩个指针以及中间元素，可以肯定的是如果中间元素比最左边的值大那说明最小值肯定在右边(左边的小递增数组特性)，如果中间元素比最右边的值小那说明最小值肯定在左边(右边的小递增数组特性)，到这一步的时候就需要拿数字举例一下看到底应该怎么找到最小值，最终举例完以后会发现按照上面的思路最终左边的指针和右边的指针相差1的时候，右边的指针指向的就是最小的元素(在解题没有思路的时候拿实际数据算一下然后找出其中的规律，我们的算法说白了就是把这个规律用程序表达出来)。最后考虑一些异常的情况：中间元素比最左边的值大的时候最小值肯定在右边吗？不一定，考虑数组{1,0,1,1,1}的情况，因此当最左边元素和中间元素以及最右边元素值相同的时候，就不能再使用二分法进行查找了
(末尾附上二分查找代码)

public class Eight {
	public static void main(String[] args) {
		int[] arr = {3,4,5,1,2};
		System.out.println(findMin(arr));
		int[] brr = {1,0,1,1,1};
		System.out.println(findMin(brr));
		int[] crr = {1,1,1,0,1};
		System.out.println(findMin(crr));
		int[] drr = {5,4,3,2,1};
		System.out.println(findMin(drr));
	}
	public static int findMin(int[] arr) {
		if (arr.length <= 0) {
			throw new Error("input error");
		}
		int start = 0;
		int end = arr.length - 1;
		if (arr[start] < arr[end]) {
			return arr[start];
		}
		while(arr[start] >= arr[end]) {
			if (start + 1 == end) {
				return arr[end];
			}
			int mid = (start + end) / 2;
			if (arr[start] == arr[mid] && arr[end] == arr[mid]) {
				int val = arr[start];
				for (int idx = start + 1;idx <= end;idx++) {
					if (val > arr[idx]) {
						val = arr[idx];
					}
				}
				return val;
			}
			if (arr[mid] >= arr[start]) {
				start = mid;
			} else if (arr[mid] <= arr[end]) {
				end = mid;
			} else {
				break;
			}
		}
		throw new Error("input error");
	}
}
//附上二分法查找
public class Erfen {
	public static void main(String[] args) {
		int[] arr = {1,2,3,4,11,17,18};
		System.out.println(erfen(arr,12));
		System.out.println(erfen(arr,18));
		System.out.println(erfen(arr,1));
		System.out.println(erfen(arr,11));

	}
	public static int erfen(int[] arr,int val) {
		int start = 0;
		int end = arr.length - 1;
		while(start <= end) {
			int mid = (start + end) / 2;
			if (arr[mid] == val) {
				return mid;
			} else if (arr[mid] < val) {
				start = mid + 1;
			} else {
				end = mid - 1;
			}
		}
		return -1;
	}
}
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