本文主要是介绍求旋转数组的最小数字——二分查找算法的深入理解，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
没想到啊，没想到，面试第一家互联网企业的时候，就是这一问题。之前又看到过这个题型，但是没有自己动手写过代码，所以花了一些时间才想出思路来，真是汗颜。在这里重新做一下思路总结。
二分查找算法，针对一个有序的数组，可以有O(log2n)的时间复杂度。那对于相对有序的数组，比如旋转数组，array1[]={4,5,1,2,3}，这种情况下如何查找数组当中的最小值？
思路：其实还是用二分查找的思路，如果二分查找的两个指针两头就是指向一个排序的数组，那就好办了。那两个指针之间不是排序的呢？那就调整其中一个指针使得他们两个之间的数组是排序的。就是说先判断旋转数组头和尾的数的大小，那边大就调整哪边的指针，比如，如果左边的大，那么将左边的指针往右移，移多少呢，移一半（left+right）/2个单位。如果右边大，那就移动右边的指针一半的单位，知道两个指针指向相邻的两个元素时，在比较左右两个元素谁最小。返回下标值，结束。
点评：1二分查找法；2分析能力；3还是要把情况想完整，想清楚。
// FindMinofRotatedArray.cpp : 定义控制台应用程序的入口点。
/*@mishidemudong@2015-6-2-10:27
*/
//#include "stdafx.h"int Min(int * numbers, int length)
{if (numbers == NULL || length <= 0)return -1;int first = 0;int end = length-1;int mid = first;while (numbers[first] >= numbers[end]){if ((end - first == 1)||(first-end==1))//注意end会跑到first前面，所以这里的条件是两个；{mid = end;break;}mid = (first + end) / 2;if (numbers[mid] >= numbers[first])first = mid;else if (numbers[mid] <= numbers[first])end = mid;}return mid;
}int _tmain(int argc, _TCHAR* argv[])
{int result1 = 0;int result2 = 0;int result3 = 0;int result4 = 0;int array1[] = { 5, 1, 2 ,3, 4 };int array2[] = { 1, 2, 3, 4, 5 };int array3[] = { 4, 5, 1, 2, 3 };int array4[] = { 3, 4, 5, 1, 1 };result1 = Min(array1, 5);result2 = Min(array2, 5);result3 = Min(array3, 5);result4 = Min(array4, 5);for (int i = 0; i < 5; ++i)printf("%d ", array1[i]);printf("\n%d\n ", result1);for (int i = 0; i < 5; ++i)printf("%d ", array2[i]);printf("\n%d\n ", result2);for (int i = 0; i < 5; ++i)printf("%d ", array3[i]);printf("\n%d\n", result3);for (int i = 0; i < 5; ++i)printf("%d ", array4[i]);printf("\n%d\n", result4);return 0;}
这篇关于求旋转数组的最小数字——二分查找算法的深入理解的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
