By

文章目录
  1. 1. Naive解法
  2. 2. 改进的解法
  3. 3. 总结

来自《剑指Offer》中的一道面试题：

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个非递减的排序的数组的一个旋转，输出旋转数组的最小元素。例如数组 {3, 4, 5, 1, 2} 为 {1, 2, 3, 4, 5} 的一个旋转， 该数组的最小元素为 1。

理清了算法思路后写出了代码，后面看了书上的解法，觉得有些不直观，分享下自己的代码；）

Naive解法

在 O(n) 时间范围内遍历旋转后的数组，可以找到最小的元素。但是，这种解法没有利用旋转数组的特点，即数组内部元素间部分有序，因此，查找效率不高。

改进的解法

旋转数组是对非递增的排序的数组进行旋转的结果，因此，数组内部元素被分为了2个区间，在各区间内部是有序的，例如 {3, 4, 5, 1, 2} ，被分为了 {3, 4, 5 } 和 { 1, 2} 两个有序的子区间，对于有序的数组的查找问题，可以考虑二分查找算法，时间复杂度 O(log(n))。

那么，如何对旋转的数组采用二分查找法寻找最小的元素呢，基本思路如下：

  1. 对旋转数组二分， 必然有一个区间内的元素间是严格的非递增有序的；
  2. 比较中间的元素与二分后两个区间的元素，可以筛选掉一个区间的元素；
  3. 再二分，再重复第二步骤，直到中间的元素都不大于二分后两个区间内的元素。

呃，感觉还是confusing，上菜：

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
int findMin(int numbers[], int size){
    if(numbers == NULL || size == 0){
        throw new exception("Invalid parameters");
    }

    int low = 0, high = size - 1, mid = 0;

    while(low < high){
	    mid = (low + high) >> 1;

	    if(A[low] < A[high]){ //数组是严格非递增排序的
		    break;
	    }else if(A[low] == A[high]){ // 见下方 `dateset6` 情况
		    high--;
	    }else if(A[low] > A[high]){
		    if(A[mid] >= A[low]){ // 最小元素必在 mid 位置后的子区间，因为包括mid索引的元素之前的元素排序是递增的
			    low = mid + 1;
		    }else{                 
				high = mid; // 有可能 mid 索引的元素就是最小元素
		    }
	    }
    }

    return A[low];
}

测试数据：

1
2
3
4
5
6
dataset1: {4, 5, 1, 2, 3}
dataset2: {5, 1, 2, 3, 4}
dataset3: {1, 2, 3, 4, 5}
dataset4: {2, 3, 4, 5, 1}
dataset5: {3, 4, 5, 1, 2}
dataset6: {1, 1, 1, 0, 1}

总结

二分查找算法在面试题中经常遇到，算法很简单，但非常重要，面试题经常会以各种变化的形式[^1]考察。当看到对有序或部分有序的数组进行查找时，可以考虑用二分查找算法。

[^1]: 《剑指Offer》中另一道面试题：统计一个数字在排序数组中出现的次数。例如输入排序数组 {1, 2, 3, 3, 3, 3, 4, 5}, 由于 3 在这个数组中出现了 4 次，因此输出 4。

文章目录
  1. 1. Naive解法
  2. 2. 改进的解法
  3. 3. 总结